Skip to main content
Talentd

Make Array Elements Equal to Zero - Solution & Explanation

EasyArraySimulationPrefix Sum20 min readAsked at: Amazon, Microsoft, Meta +2
Practice this problem

Problem Statement

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.

 

Example 1:

Input: nums = [1,0,2,0,3]

Output: 2

Explanation:

The only possible valid selections are the following:

  • Choose 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].
  • Choose 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 <= 100
  • 0 <= nums[i] <= 100
  • There is at least one element i where nums[i] == 0.

Approach Overview

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.

Approach 1: Simulation with State Changes

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.

Code

CPythonC++JavaC#JavaScript

C

Python

C++

Java

C#

JavaScript

Complexity

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.

Try this approach in the editor →

Approach 2: Graph Approach with BFS

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.

Code

C++PythonJava

C++

Python

Java

Complexity

Time Complexity: O(n^2), Space Complexity: O(n) for queue storage and a temp copy of nums.

Try this approach in the editor →

Approach 3: Enumeration + Prefix Sum

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).

Code

PythonJavaC++GoTypeScriptRustC#

Python

Java

C++

Go

TypeScript

Rust

C#

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
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—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Simulation with State ChangesO(n)O(1)Best for understanding the mechanics of the operation and implementing the straightforward logic.
Prefix Sum ReasoningO(n)O(1)Preferred in interviews for a clean linear scan that avoids repeated state updates.
Graph Approach with BFSO(n)O(n)Useful when modeling propagation of changes across indices or explaining the process as a traversal.

Video Solution

Make Array Elements Equal to Zero | Brute Force | Optimal | Detailed Dry Runs | Leetcode 3354 | MIK • codestorywithMIK • 6,499 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Make Array Elements Equal to Zero easy or hard?
LeetCode classifies this problem as Easy with an acceptance rate around 68%. The difficulty comes mainly from understanding how operations affect future elements rather than implementing complex data structures.
Make Array Elements Equal to Zero Python/Java solution
A typical Python or Java implementation performs a single pass through the array while maintaining a running value that represents the cumulative effect of operations. Each step checks whether the adjusted element can reach zero and updates the running state accordingly.
How to solve Make Array Elements Equal to Zero in O(n)?
Traverse the array while maintaining a running prefix effect that represents operations already applied. For each element, compute its effective value after previous operations. If the adjusted value violates the required conditions, the array cannot be reduced to zero; otherwise continue scanning. This avoids repeatedly modifying elements and guarantees O(n) time.
What is the best approach for Make Array Elements Equal to Zero?
The most practical approach uses a linear scan with simulation or prefix-sum reasoning. You track the cumulative effect of operations while iterating through the array and ensure each element can be reduced to zero under those adjustments. This keeps the runtime O(n) with constant extra space.
Is Make Array Elements Equal to Zero asked at Google/Amazon/Meta?
Problems involving array simulation, prefix sums, and state propagation frequently appear in interviews at companies like Amazon, Google, and Meta. While the exact problem may vary, the underlying pattern of modeling cumulative operations across an array is common.
What data structure is used in Make Array Elements Equal to Zero?
The core structure is a simple array combined with running prefix calculations. Some explanations also frame the process as a graph traversal using a queue for BFS when modeling how updates propagate between neighboring indices.
What is the time complexity of Make Array Elements Equal to Zero?
The optimal solution runs in O(n) time because the array is processed once while maintaining the cumulative impact of operations. Space complexity is typically O(1) since only a few running variables are required.

Ready to solve this problem?

Practice Make Array Elements Equal to Zero with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays