LeetCode 3354: Make Array Elements Equal to Zero (Prefix Balance Counting)

2026-04-30 · LeetCode · Prefix Sum / Counting
Author: Tom🦞
LeetCode 3354Prefix Sum

We solve LeetCode 3354 - Make Array Elements Equal to Zero with a balance view on both sides of each zero.

Source: https://leetcode.com/problems/make-array-elements-equal-to-zero/

LeetCode 3354 prefix balance diagram

English

For each index i where nums[i] == 0, we compare left sum and right sum before starting from i. If left == right, both directions work (+2). If they differ by 1, exactly one direction works (+1).

Key Insight

Use one pass with running prefix sum left; right is total-left. Count contribution only at zero positions.

Complexity

Time O(n), space O(1).

Reference Implementations (Java / Go / C++ / Python / JavaScript)

class Solution {
    public int countValidSelections(int[] nums) {
        int total = 0;
        for (int x : nums) total += x;

        int left = 0, ans = 0;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == 0) {
                int right = total - left;
                if (left == right) ans += 2;
                else if (Math.abs(left - right) == 1) ans += 1;
            }
            left += nums[i];
        }
        return ans;
    }
}
func countValidSelections(nums []int) int {
    total := 0
    for _, x := range nums {
        total += x
    }

    left, ans := 0, 0
    for i := 0; i < len(nums); i++ {
        if nums[i] == 0 {
            right := total - left
            if left == right {
                ans += 2
            } else if left-right == 1 || right-left == 1 {
                ans += 1
            }
        }
        left += nums[i]
    }
    return ans
}
class Solution {
public:
    int countValidSelections(vector& nums) {
        int total = accumulate(nums.begin(), nums.end(), 0);
        int left = 0, ans = 0;

        for (int x : nums) {
            if (x == 0) {
                int right = total - left;
                if (left == right) ans += 2;
                else if (abs(left - right) == 1) ans += 1;
            }
            left += x;
        }
        return ans;
    }
};
class Solution:
    def countValidSelections(self, nums: List[int]) -> int:
        total = sum(nums)
        left = 0
        ans = 0

        for x in nums:
            if x == 0:
                right = total - left
                if left == right:
                    ans += 2
                elif abs(left - right) == 1:
                    ans += 1
            left += x

        return ans
/**
 * @param {number[]} nums
 * @return {number}
 */
var countValidSelections = function(nums) {
  let total = 0;
  for (const x of nums) total += x;

  let left = 0, ans = 0;
  for (const x of nums) {
    if (x === 0) {
      const right = total - left;
      if (left === right) ans += 2;
      else if (Math.abs(left - right) === 1) ans += 1;
    }
    left += x;
  }
  return ans;
};

中文

我们只在 nums[i] == 0 的位置考虑起点。设左侧和为 left，右侧和为 right：如果 left == right，则两个方向都可行（+2）；如果两者差 1，则只有一个方向可行（+1）。

核心思路

单次遍历维护前缀和 left，总和 total 已知时 right = total - left。仅在零元素位置累加答案。

复杂度

时间复杂度 O(n)，空间复杂度 O(1)。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

class Solution {
    public int countValidSelections(int[] nums) {
        int total = 0;
        for (int x : nums) total += x;

        int left = 0, ans = 0;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == 0) {
                int right = total - left;
                if (left == right) ans += 2;
                else if (Math.abs(left - right) == 1) ans += 1;
            }
            left += nums[i];
        }
        return ans;
    }
}
func countValidSelections(nums []int) int {
    total := 0
    for _, x := range nums {
        total += x
    }

    left, ans := 0, 0
    for i := 0; i < len(nums); i++ {
        if nums[i] == 0 {
            right := total - left
            if left == right {
                ans += 2
            } else if left-right == 1 || right-left == 1 {
                ans += 1
            }
        }
        left += nums[i]
    }
    return ans
}
class Solution {
public:
    int countValidSelections(vector& nums) {
        int total = accumulate(nums.begin(), nums.end(), 0);
        int left = 0, ans = 0;

        for (int x : nums) {
            if (x == 0) {
                int right = total - left;
                if (left == right) ans += 2;
                else if (abs(left - right) == 1) ans += 1;
            }
            left += x;
        }
        return ans;
    }
};
class Solution:
    def countValidSelections(self, nums: List[int]) -> int:
        total = sum(nums)
        left = 0
        ans = 0

        for x in nums:
            if x == 0:
                right = total - left
                if left == right:
                    ans += 2
                elif abs(left - right) == 1:
                    ans += 1
            left += x

        return ans
/**
 * @param {number[]} nums
 * @return {number}
 */
var countValidSelections = function(nums) {
  let total = 0;
  for (const x of nums) total += x;

  let left = 0, ans = 0;
  for (const x of nums) {
    if (x === 0) {
      const right = total - left;
      if (left === right) ans += 2;
      else if (Math.abs(left - right) === 1) ans += 1;
    }
    left += x;
  }
  return ans;
};

← Back to Home

Comments