3354. Make Array Elements Equal to Zero - Solution

Q: 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.

Q: 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.

Q: 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.

Q: 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.

Q: 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.

Q: 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.

Q: 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.

The problem

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.

Python

def numberOfValidSelections(nums):
    def canConvertAllToZero(start, direction):
        temp = nums[:]
        curr = start
        while 0 <= curr < len(nums):
            if temp[curr] > 0:
                temp[curr] -= 1
                direction = -direction
            curr += direction
        return all(x == 0 for x in temp)
    
    validSelections = 0
    for i in range(len(nums)):
        if nums[i] == 0:
            if canConvertAllToZero(i, 1):
                validSelections += 1
            if canConvertAllToZero(i, -1):
                validSelections += 1
    return validSelections

print(numberOfValidSelections([1, 0, 2, 0, 3]))

Java

import java.util.Arrays;

public class Main {
    public static void main(String[] args) {
        int[] nums = {1, 0, 2, 0, 3};
        System.out.println(numberOfValidSelections(nums));
    }

    public static int numberOfValidSelections(int[] nums) {
        int validSelections = 0;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == 0) {
                if (canConvertToZero(nums, i, 1)) {
                    validSelections++;
                }
                if (canConvertToZero(nums, i, -1)) {
                    validSelections++;
                }
            }
        }
        return validSelections;
    }

    private static boolean canConvertToZero(int[] nums, int start, int direction) {
        int[] temp = Arrays.copyOf(nums, nums.length);
        int curr = start;
        while (curr >= 0 && curr < nums.length) {
            if (temp[curr] > 0) {
                temp[curr]--;
                direction = -direction;
            }
            curr += direction;
        }
        return Arrays.stream(temp).allMatch(x -> x == 0);
    }
}

C++

#include <vector>
#include <algorithm>

int numberOfValidSelections(std::vector<int>& nums) {
    auto canConvertToZero = [&](int start, int direction) {
        std::vector<int> temp(nums);
        int curr = start;
        while (curr >= 0 && curr < nums.size()) {
            if (temp[curr] > 0) {
                temp[curr] -= 1;
                direction = -direction;
            }
            curr += direction;
        }
        return std::all_of(temp.begin(), temp.end(), [](int x) { return x == 0; });
    };

    int validSelections = 0;
    for (int i = 0; i < nums.size(); ++i) {
        if (nums[i] == 0) {
            if (canConvertToZero(i, 1))
                ++validSelections;
            if (canConvertToZero(i, -1))
                ++validSelections;
        }
    }
    return validSelections;
}

int main() {
    std::vector<int> nums = {2, 3, 4, 0, 4, 1, 0};
    int result = numberOfValidSelections(nums);
    std::cout << result << std::endl;
    return 0;
}

JavaScript

function numberOfValidSelections(nums) {
    function canConvertAllToZero(start, direction) {
        let temp = nums.slice();
        let curr = start;
        while (curr >= 0 && curr < nums.length) {
            if (temp[curr] > 0) {
                temp[curr] -= 1;
                direction = -direction;
            }
            curr += direction;
        }
        return temp.every(x => x === 0);
    }
    
    let validSelections = 0;
    for (let i = 0; i < nums.length; i++) {
        if (nums[i] === 0) {
            if (canConvertAllToZero(i, 1)) {
                validSelections++;
            }
            if (canConvertAllToZero(i, -1)) {
                validSelections++;
            }
        }
    }
    return validSelections;
}

console.log(numberOfValidSelections([1, 0, 2, 0, 3]));

#include <stdbool.h>
#include <stdio.h>
#include <string.h>

int numberOfValidSelections(int* nums, int numsSize) {
    int validSelections = 0;
    for (int i = 0; i < numsSize; ++i) {
        if (nums[i] == 0) {
            int temp[numsSize];
            memcpy(temp, nums, numsSize * sizeof(int));
            // Try left direction
            int curr = i, direction = -1;
            bool valid = true;
            while (curr >= 0 && curr < numsSize) {
                if (temp[curr] > 0) {
                    temp[curr]--;
                    direction = -direction;
                }
                curr += direction;
            }
            for (int j = 0; j < numsSize; ++j) {
                if (temp[j] != 0) {
                    valid = false;
                    break;
                }
            }
            if (valid) validSelections++;

            // Try right direction
            memcpy(temp, nums, numsSize * sizeof(int));
            curr = i;
            direction = 1;
            valid = true;
            while (curr >= 0 && curr < numsSize) {
                if (temp[curr] > 0) {
                    temp[curr]--;
                    direction = -direction;
                }
                curr += direction;
            }
            for (int j = 0; j < numsSize; ++j) {
                if (temp[j] != 0) {
                    valid = false;
                    break;
                }
            }
            if (valid) validSelections++;
        }
    }
    return validSelections;
}

int main() {
    int nums[] = {1, 0, 2, 0, 3};
    int result = numberOfValidSelections(nums, sizeof(nums)/sizeof(nums[0]));
    printf("%d\n", result);
    return 0;
}

using System;

public class Program {
    public static void Main() {
        int[] nums = {1, 0, 2, 0, 3};
        Console.WriteLine(NumberOfValidSelections(nums));
    }

    public static int NumberOfValidSelections(int[] nums) {
        int validSelections = 0;
        for (int i = 0; i < nums.Length; i++) {
            if (nums[i] == 0) {
                if (CanConvertToZero(nums, i, 1)) {
                    validSelections++;
                }
                if (CanConvertToZero(nums, i, -1)) {
                    validSelections++;
                }
            }
        }
        return validSelections;
    }

    private static bool CanConvertToZero(int[] nums, int start, int direction) {
        int[] temp = (int[])nums.Clone();
        int curr = start;
        while (curr >= 0 && curr < nums.Length) {
            if (temp[curr] > 0) {
                temp[curr]--;
                direction = -direction;
            }
            curr += direction;
        }
        foreach (int num in temp) {
            if (num != 0) return false;
        }
        return true;
    }
}

The Python solution uses a helper function canConvertAllToZero that tries to transform the given array into all zeros from a starting zero index, checking and flipping directions when needed. Each zero in the array becomes a potential start point, and each direction is tested independently.

Complexity

Time Complexity: O(n^2), Space Complexity: O(n) due to using additional space for the temporary list.

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.

Python

from collections import deque

def numberOfValidSelections(nums):
    n = len(nums)

    def bfs(start, direction):
        q = deque([(start, direction)])
        temp = nums[:]

        while q:
            curr, dir = q.popleft()
            if curr < 0 or curr >= n:
                continue

            if temp[curr] > 0:
                temp[curr] -= 1
                dir = -dir

            if temp[curr] == 0:
                q.append((curr + dir, dir))

        return all(x == 0 for x in temp)

    validSelections = 0
    for i in range(n):
        if nums[i] == 0:
            if bfs(i, 1):
                validSelections += 1
            if bfs(i, -1):
                validSelections += 1
    return validSelections

print(numberOfValidSelections([1, 0, 2, 0, 3]))

Java

import java.util.*;

public class Main {
    public static void main(String[] args) {
        int[] nums = {1, 0, 2, 0, 3};
        System.out.println(numberOfValidSelections(nums));
    }

    public static int numberOfValidSelections(int[] nums) {
        int n = nums.length;
        int validSelections = 0;
        for (int i = 0; i < n; i++) {
            if (nums[i] == 0) {
                if (bfs(nums, i, 1)) validSelections++;
                if (bfs(nums, i, -1)) validSelections++;
            }
        }
        return validSelections;
    }

    private static boolean bfs(int[] nums, int start, int direction) {
        Queue<int[]> q = new LinkedList<>();
        q.offer(new int[]{start, direction});
        int[] temp = Arrays.copyOf(nums, nums.length);

        while (!q.isEmpty()) {
            int[] current = q.poll();
            int curr = current[0];
            int dir = current[1];

            if (curr < 0 || curr >= nums.length)
                continue;

            if (temp[curr] > 0) {
                temp[curr]--;
                dir = -dir;
            }

            if (temp[curr] == 0)
                q.offer(new int[]{curr + dir, dir});
        }

        return Arrays.stream(temp).allMatch(x -> x == 0);
    }
}

C++

#include <vector>
#include <queue>
#include <cstring>

int numberOfValidSelections(std::vector<int> nums) {
    int n = nums.size();
    int validSelections = 0;
    auto bfs = [&](int start, int direction) {
        std::queue<std::pair<int, int>> q;
        q.push({start, direction});
        std::vector<int> temp = nums;

        while (!q.empty()) {
            auto [curr, dir] = q.front();
            q.pop();

            if (curr < 0 || curr >= n)
                continue;

            if (temp[curr] > 0) {
                temp[curr]--;
                dir = -dir;
            }

            if (temp[curr] == 0)
                q.push({curr + dir, dir});
        }

        return std::all_of(temp.begin(), temp.end(), [](int x) { return x == 0; });
    };

    for (int i = 0; i < n; ++i) {
        if (nums[i] == 0) {
            if (bfs(i, 1)) validSelections++;
            if (bfs(i, -1)) validSelections++;
        }
    }

    return validSelections;
}

int main() {
    std::vector<int> nums = {1, 0, 2, 0, 3};
    int result = numberOfValidSelections(nums);
    std::cout << result << '\n';
    return 0;
}

Implement BFS using a queue, where zeros are start points and each move results in an evaluation if the path can lead to zeroing all elements. Each direction is explored separately for potential validity as an answer.

Complexity

Time Complexity: O(n^2), Space Complexity: O(n) due to using a queue and a copy of the list during each BFS run.

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

TypeScript

function countValidSelections(nums: number[]): number {
    const s = nums.reduce((acc, x) => acc + x, 0);
    let [ans, l] = [0, 0];
    for (const x of nums) {
        if (x) {
            l += x;
        } else if (l * 2 === s) {
            ans += 2;
        } else if (Math.abs(l * 2 - s) <= 1) {
            ++ans;
        }
    }
    return ans;
}

func countValidSelections(nums []int) (ans int) {
	l, s := 0, 0
	for _, x := range nums {
		s += x
	}
	for _, x := range nums {
		if x != 0 {
			l += x
		} else if l*2 == s {
			ans += 2
		} else if abs(l*2-s) <= 1 {
			ans++
		}
	}
	return
}

func abs(x int) int {
	if x < 0 {
		return -x
	}
	return x
}

Rust

impl Solution {
    pub fn count_valid_selections(nums: Vec<i32>) -> i32 {
        let s: i32 = nums.iter().sum();
        let mut ans = 0;
        let mut l = 0;
        for &x in &nums {
            if x != 0 {
                l += x;
            } else if l * 2 == s {
                ans += 2;
            } else if (l * 2 - s).abs() <= 1 {
                ans += 1;
            }
        }
        ans
    }
}

Try this approach in the editor

Complexity comparison

Approach	Complexity
Simulation with State Changes	Time Complexity: O(n^2), Space Complexity: O(n) due to using additional space for the temporary list.
Graph Approach with BFS	Time Complexity: O(n^2), Space Complexity: O(n) due to using a queue and a copy of the list during each BFS run.
Enumeration + Prefix Sum	–

Complexity analysis

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.

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.

Make Array Elements Equal to Zero solution and explanation

The problem

Approach overview

Approach 1: Simulation with State Changes

Approach 2: Graph Approach with BFS

Approach 3: Enumeration + Prefix Sum

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Make Array Elements Equal to Zero solution and explanation

The problem

Approach overview

Approach 1: Simulation with State Changes

Approach 2: Graph Approach with BFS

Approach 3: Enumeration + Prefix Sum

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems