Make array elements equal to zero

Array Simulation Prefix Sum

68.3% acceptance

Feb 24, 2026

554

165

You are given an integer array nums. Start by selecting a starting position curr such that nums[curr] == 0, and choose a movement direction of either left or right. After that, you repeat the following process: If curr is out of the range [0, n - 1], this process ends. If nums[curr] == 0, move in the current direction by incrementing curr if you are moving right, or decrementing curr if you are moving left. Else if nums[curr] > 0: Decrement nums[curr] by 1. Reverse your movement direction (left becomes right and vice versa). Take a step in your new direction. A selection of the initial position curr and movement direction is considered valid if every element in nums becomes 0 by the end of the process. Return the number of possible valid selections.

Solution

Rust

Time O(n)

Space O(1)

LeetCode

solution.rs

impl Solution {
  pub fn count_valid_selections(nums: Vec<i32>) -> i32 {
    // For a zero at position p:
    // - sum of elements to the left = sum_left
    // - sum of elements to the right = sum_right
    // Starting left: the bouncing process from p heading left will work iff
    //   the total sum on each side balances properly.
    // Key insight: starting at p going left: all elements get zeroed iff sum_left == sum_right
    //   OR sum_right == sum_left + 1 (the process "allocates" one extra bounce toward right).
    // Actually: for zero at index p, starting direction left:
    //   valid iff sum_left == sum_right (exact balance) [direction left means we go left first, bounce on leftmost nonzero, etc.]
    //   It's a classic problem: valid iff |sum_left - sum_right| <= 1
    //   Starting left is valid iff sum_left == sum_right OR sum_left == sum_right - 1
    //   Starting right is valid iff sum_right == sum_left OR sum_right == sum_left - 1
    //   (i.e., starting left: sum_right >= sum_left, difference <= 1;
    //          starting right: sum_left >= sum_right, difference <= 1)
    
    let n = nums.len();
    let total: i32 = nums.iter().sum();
    let mut count = 0;
    let mut left_sum = 0i32;
    
    for i in 0..n {
      if nums[i] == 0 {
        let right_sum = total - left_sum;
        // Start going left: valid if right_sum - left_sum <= 1 and right_sum >= left_sum - 1
        // Actually: going left first means we need left_sum <= right_sum <= left_sum + 1
        // No wait, let me re-derive:
        // From a zero at p going left: we'll process elements on the left side (alternating),
        // then once we exit left, process right side. Works if sum_left == sum_right (exit both ends)
        // or exact conditions.
        // Simpler: p going left valid iff sum_left == sum_right OR sum_right == sum_left + 1
        // p going right valid iff sum_left == sum_right OR sum_left == sum_right + 1
        if right_sum == left_sum || right_sum == left_sum + 1 {
          count += 1; // start going left
        }
        if left_sum == right_sum || left_sum == right_sum + 1 {
          count += 1; // start going right
        }
        // But if both conditions hold (sum_left==sum_right), we count both
      }
      left_sum += nums[i];
    }
    count
  }
}