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:
curr is out of the range [0, n - 1], this process ends.nums[curr] == 0, move in the current direction by incrementing curr if you are moving right, or decrementing curr if you are moving left.nums[curr] > 0:
nums[curr] by 1.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.
Example 1:
Input: nums = [1,0,2,0,3]
Output: 2
Explanation:
The only possible valid selections are the following:
curr = 3, and a movement direction to the left.
[1,0,2,0,3] -> [1,0,2,0,3] -> [1,0,1,0,3] -> [1,0,1,0,3] -> [1,0,1,0,2] -> [1,0,1,0,2] -> [1,0,0,0,2] -> [1,0,0,0,2] -> [1,0,0,0,1] -> [1,0,0,0,1] -> [1,0,0,0,1] -> [1,0,0,0,1] -> [0,0,0,0,1] -> [0,0,0,0,1] -> [0,0,0,0,1] -> [0,0,0,0,1] -> [0,0,0,0,0].curr = 3, and a movement direction to the right.
[1,0,2,0,3] -> [1,0,2,0,3] -> [1,0,2,0,2] -> [1,0,2,0,2] -> [1,0,1,0,2] -> [1,0,1,0,2] -> [1,0,1,0,1] -> [1,0,1,0,1] -> [1,0,0,0,1] -> [1,0,0,0,1] -> [1,0,0,0,0] -> [1,0,0,0,0] -> [1,0,0,0,0] -> [1,0,0,0,0] -> [0,0,0,0,0].Example 2:
Input: nums = [2,3,4,0,4,1,0]
Output: 0
Explanation:
There are no possible valid selections.
Constraints:
1 <= nums.length <= 1000 <= nums[i] <= 100i where nums[i] == 0.Problem Overview: You are given an integer array and must determine whether the elements can be reduced so the entire array becomes zero under the allowed operations. The key challenge is tracking how values change as operations propagate across the array.
Approach 1: Simulation with State Changes (O(n) time, O(1) space)
The most direct strategy is to simulate the process exactly as defined. Iterate through the array and apply the allowed operation whenever a valid state appears. Each operation updates the current element and may influence neighboring positions, so you maintain the array state as you move through it. The insight is that every value eventually contributes to a sequence of decrements that propagate across the array. Because each element is processed a constant number of times, the total time complexity remains O(n) with O(1) extra space. This approach is ideal when the constraints are small or when the goal is to mirror the problem statement precisely using straightforward array traversal.
Approach 2: Prefix Sum Based Reasoning (O(n) time, O(1) space)
Instead of explicitly performing every state change, you can track the cumulative effect of operations using a running prefix balance. Each operation contributes a predictable change that affects future positions. By maintaining a prefix sum that represents the total operations applied so far, you can determine the effective value of the current element without modifying the entire array. If the adjusted value becomes invalid at any step, the configuration cannot reach all zeros. This reduces unnecessary updates and keeps the algorithm strictly linear. Prefix tracking is a common optimization pattern when operations apply cumulative changes across an prefix sum structure.
Approach 3: Graph Perspective with BFS (O(n) time, O(n) space)
The array can also be viewed as a graph where each index is a node and operations propagate changes to adjacent indices. In this interpretation, nodes that become zero act as starting points that trigger updates to neighbors. Using a queue, perform a breadth‑first search that processes indices whose state allows further propagation. Each node is visited when its value reaches the required condition, and the BFS ensures updates spread in the correct order. This framing is helpful when reasoning about chained effects or when the operation behaves like a wave spreading through the array. The queue introduces O(n) auxiliary space but keeps the runtime linear. This method combines array traversal with classic simulation ideas.
Recommended for interviews: The simulation approach is usually the first step because it mirrors the problem statement and proves you understand the state transitions. Interviewers typically expect you to then optimize the reasoning using a prefix‑sum style running balance, which avoids repeated updates and achieves a clean O(n) solution.
This approach involves simulating each possible valid selection by maintaining the current index and direction. You start at zero indices, trying each direction, and check if all elements can be turned to zeros by modifying states directly.
The simulation checks every zero index as a potential starting point. For each direction, it modifies the given 'nums' array and toggles direction whenever a positive number is encountered until all numbers are zero or out of bounds. It verifies at every end of these movements if all zeros are achieved.
Time Complexity: O(n^2) where n is the number of elements in the array. Space Complexity: O(n) since we're using a temporary array clone.
Recognize the problem as a graph traversal issue, viewing each element as a vertex connected by its indices. Treat increments and direction changes as edge conditions, and use breadth-first search (BFS) to examine potential paths that achieve the goal of zeroing the array elements.
This method represents each zero starting point as an initial BFS vertex. By enqueuing changes in position, we explore through adjacent nodes simulating the decrement and direction reversal process, applying standard BFS until all nodes reach zero or the simulation is stopped.
Time Complexity: O(n^2), Space Complexity: O(n) for queue storage and a temp copy of nums.
Suppose we initially move to the left and encounter a non-zero element. In that case, we need to decrement this element by one, then change the direction of movement and continue moving.
Therefore, we can maintain the sum of elements to the left of each zero-value element as l, and the sum of elements to the right as s - l. If l = s - l, meaning the sum of elements on the left equals the sum of elements on the right, we can choose the current zero-value element and move either left or right, adding 2 to the answer. If |l - (s - l)| = 1, and the sum of elements on the left is greater, we can choose the current zero-value element and move left, adding 1 to the answer. If the sum of elements on the right is greater, we can choose the current zero-value element and move right, adding 1 to the answer.
The time complexity is O(n), where n is the length of the array. The space complexity is O(1).
| Approach | Complexity |
|---|---|
| Simulation with State Changes | Time Complexity: O(n^2) where n is the number of elements in the array. Space Complexity: O(n) since we're using a temporary array clone. |
| Graph Approach with BFS | Time Complexity: O(n^2), Space Complexity: O(n) for queue storage and a temp copy of nums. |
| Enumeration + Prefix Sum | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Simulation with State Changes | O(n) | O(1) | Best for understanding the mechanics of the operation and implementing the straightforward logic. |
| Prefix Sum Reasoning | O(n) | O(1) | Preferred in interviews for a clean linear scan that avoids repeated state updates. |
| Graph Approach with BFS | O(n) | O(n) | Useful when modeling propagation of changes across indices or explaining the process as a traversal. |
Make Array Elements Equal to Zero | Brute Force | Optimal | Detailed Dry Runs | Leetcode 3354 | MIK • codestorywithMIK • 6,323 views views
Watch 9 more video solutions →Practice Make Array Elements Equal to Zero with our built-in code editor and test cases.
Practice on FleetCode