Transform array to all equal elements

Array Greedy

33.0% acceptance

Feb 25, 2026

You are given an integer array nums of size n containing only 1 and -1, and an integer k. Choose an index i and multiply both nums[i] and nums[i+1] by -1, at most k times. Return true if you can make all elements equal.

Solution

Rust

Time O(n²)

Space O(1)

LeetCode

solution.rs

impl Solution {
  pub fn can_make_equal(nums: Vec<i32>, k: i32) -> bool {
    let n = nums.len();
    // Try making all 1s or all -1s
    for target in [1i32, -1i32] {
      // Greedy: scan left to right.
      // carry = 1 if we flipped at position i-1 (so position i is inverted vs original).
      let mut ops = 0i32;
      let mut carry = 0i32;
      let mut ok = true;
      for i in 0..n {
        // Effective value at i = nums[i] * (-1)^carry
        let val = nums[i] * if carry == 0 { 1 } else { -1 };
        if val != target {
          if i == n - 1 {
            ok = false;
            break;
          }
          // Flip at i: next position i+1 is affected -> carry = 1
          carry = 1;
          ops += 1;
        } else {
          // No flip at i: next position is NOT affected by a flip at i
          carry = 0;
        }
      }
      if ok && ops <= k {
        return true;
      }
    }
    false
  }
}