Make Array Elements Equal to Zero

Easy

#2980Time: O(Z * (n log n + S * log n)), where Z is the number of zeros, S is the sum of elements, and n is the length. For each of the `Z` starting configurations, we spend `O(n log n)` to initialize the `TreeSet`. The simulation involves `S` decrements, and each step (decrement or jump) takes `O(log n)` time. This complexity is efficient enough for the given constraints.Space: O(n), where n is the length of `nums`. Space is used for the array copy and the `TreeSet`, which can store up to `n` indices.

Patterns

Prefix Sum

Data structures

Array

Prompt

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.

Approaches

2 approaches with complexity analysis and trade-offs.

The brute-force simulation can be slow because of the time spent traversing blocks of zeros one step at a time. We can optimize this by skipping over consecutive zeros in a single operation. A TreeSet is an effective data structure for this purpose, as it can maintain the sorted indices of non-zero elements and find the next one in a given direction in logarithmic time.

Algorithm

The overall structure is the same as the brute-force approach: iterate through all (start_position, start_direction) pairs.
For each simulation, instead of a simple array, use a TreeSet to store the indices of all non-zero elements. This allows for efficient queries of the next non-zero index.
Initialize the simulation with a copy of nums, the TreeSet of non-zero indices, curr, and dir.
Loop as long as curr is within bounds: a. If nums_copy[curr] > 0: i. Decrement nums_copy[curr]. ii. If nums_copy[curr] becomes 0, remove curr from the TreeSet. iii. Reverse direction and move: dir *= -1, curr += dir. b. If nums_copy[curr] == 0: i. Instead of moving one step at a time, find the next non-zero element in the current direction using the TreeSet. ii. If moving right (dir=1), find the smallest index in the TreeSet that is greater than curr. This is done via treeSet.ceiling(curr + 1). iii. If moving left (dir=-1), find the largest index in the TreeSet that is less than curr. This is done via treeSet.floor(curr - 1). iv. If a next non-zero index is found, jump curr to that index. Otherwise, jump curr out of bounds.
After the loop terminates, the selection is valid if and only if the TreeSet of non-zero indices is empty.

Walkthrough

In this approach, we enhance the simulation by maintaining a TreeSet of indices where the array value is positive. When the simulation is at a position curr with a value of 0, instead of moving one step, we query the TreeSet to find the index of the next non-zero element in the current direction. This allows us to jump over entire blocks of zeros instantly.

For a rightward movement, treeSet.ceiling(curr + 1) gives us the next non-zero index. For a leftward movement, treeSet.floor(curr - 1) provides the previous non-zero index. If no such index exists, it means we've moved past all remaining non-zero numbers in that direction, and we can jump curr out of bounds to terminate that path segment.

When a non-zero element at an index is decremented to zero, we must remove that index from the TreeSet. This keeps our set of non-zero indices up-to-date. This optimization significantly reduces the number of steps in the simulation, especially for sparse arrays with large blocks of zeros.

1class Solution {2    public int makeArrayElementsEqualtoZero(int[] nums) {3        int n = nums.length;4        java.util.List<Integer> zeroIndices = new java.util.ArrayList<>();5        for (int i = 0; i < n; i++) {6            if (nums[i] == 0) {7                zeroIndices.add(i);8            }9        }10 11        int validCount = 0;12        for (int startIdx : zeroIndices) {13            if (isSelectionValid(nums.clone(), startIdx, 1)) {14                validCount++;15            }16            if (isSelectionValid(nums.clone(), startIdx, -1)) {17                validCount++;18            }19        }20        return validCount;21    }22 23    private boolean isSelectionValid(int[] currentNums, int startCurr, int startDir) {24        int n = currentNums.length;25        java.util.TreeSet<Integer> nonZeroIndices = new java.util.TreeSet<>();26        for (int i = 0; i < n; i++) {27            if (currentNums[i] > 0) {28                nonZeroIndices.add(i);29            }30        }31 32        if (nonZeroIndices.isEmpty()) {33            return true;34        }35 36        int curr = startCurr;37        int dir = startDir;38 39        while (curr >= 0 && curr < n) {40            if (currentNums[curr] > 0) {41                currentNums[curr]--;42                if (currentNums[curr] == 0) {43                    nonZeroIndices.remove(curr);44                }45                dir *= -1;46                curr += dir;47            } else { // currentNums[curr] == 048                if (dir == 1) {49                    Integer nextNonZero = nonZeroIndices.ceiling(curr + 1);50                    curr = (nextNonZero != null) ? nextNonZero : n;51                } else { // dir == -152                    Integer prevNonZero = nonZeroIndices.floor(curr - 1);53                    curr = (prevNonZero != null) ? prevNonZero : -1;54                }55            }56        }57 58        return nonZeroIndices.isEmpty();59    }60}

Complexity

Time

O(Z * (n log n + S * log n)), where Z is the number of zeros, S is the sum of elements, and n is the length. For each of the `Z` starting configurations, we spend `O(n log n)` to initialize the `TreeSet`. The simulation involves `S` decrements, and each step (decrement or jump) takes `O(log n)` time. This complexity is efficient enough for the given constraints.

Space

O(n), where n is the length of `nums`. Space is used for the array copy and the `TreeSet`, which can store up to `n` indices.

Trade-offs

Pros

Significantly faster than the naive simulation, especially for sparse arrays.
The time complexity is well within typical limits for competitive programming platforms.

Cons

Slightly more complex to implement due to the use of a TreeSet.

This approach directly translates the process described in the problem into code. We test every possible valid starting configuration. A starting configuration is defined by an initial index curr where nums[curr] is 0, and an initial direction (left or right).

Algorithm

Identify all initial positions curr where nums[curr] == 0.
For each such curr, iterate through the two possible initial directions: left (-1) and right (+1).
For each pair of (start_position, start_direction), perform a full simulation of the process described.
To do this, create a copy of the nums array to modify during the simulation.
Initialize curr and dir with the starting pair.
Loop as long as curr is within the array bounds [0, n-1]: a. If nums_copy[curr] == 0, move one step in the current direction: curr += dir. b. If nums_copy[curr] > 0, decrement nums_copy[curr] by 1, reverse the direction dir *= -1, and then take a step in the new direction curr += dir.
Once the loop terminates (because curr goes out of bounds), check if all elements in nums_copy have become zero.
If they are all zero, the initial selection was valid. Increment a counter for valid selections.
After checking all possible starting configurations, return the total count.

Walkthrough

For each potential start, we simulate the entire process step-by-step. We use a copy of the input array nums for each simulation to avoid interference between different test cases. The simulation proceeds by updating the current position curr, the direction dir, and the values in the array copy according to the rules. The process is guaranteed to terminate because the sum of the elements in the array is non-increasing and strictly decreases each time we encounter a positive number.

After the simulation ends (when curr moves out of the array's bounds), we verify if all elements in the copied array have been reduced to zero. If so, we count the starting configuration as a valid one.

1class Solution {2    public int makeArrayElementsEqualtoZero(int[] nums) {3        int n = nums.length;4        java.util.List<Integer> zeroIndices = new java.util.ArrayList<>();5        for (int i = 0; i < n; i++) {6            if (nums[i] == 0) {7                zeroIndices.add(i);8            }9        }10 11        int validCount = 0;12        for (int startIdx : zeroIndices) {13            // Try starting with direction right (1)14            if (isSelectionValid(nums.clone(), startIdx, 1)) {15                validCount++;16            }17            // Try starting with direction left (-1)18            if (isSelectionValid(nums.clone(), startIdx, -1)) {19                validCount++;20            }21        }22        return validCount;23    }24 25    private boolean isSelectionValid(int[] currentNums, int startCurr, int startDir) {26        int n = currentNums.length;27        int curr = startCurr;28        int dir = startDir;29 30        // The process must terminate as the sum of elements decreases.31        // A generous step limit can prevent truly infinite loops in case of flawed logic.32        long totalSum = 0;33        for(int num : currentNums) totalSum += num;34        long maxSteps = totalSum * n + 2L * n; // A safe upper bound for steps35        long steps = 0;36 37        while (curr >= 0 && curr < n && steps < maxSteps) {38            if (currentNums[curr] > 0) {39                currentNums[curr]--;40                dir *= -1;41            }42            curr += dir;43            steps++;44        }45 46        for (int num : currentNums) {47            if (num != 0) {48                return false;49            }50        }51        return true;52    }53}

Complexity

Time

O(Z * S * n), where Z is the number of zeros in `nums`, S is the sum of elements in `nums`, and n is the length of the array. In the worst case, each of the `S` decrements might be followed by a traversal of `O(n)` zeros. Given the constraints (Z, n ≤ 100, S ≤ 100*100=10000), this could be up to `100 * 10000 * 100 = 10^8` operations, which might be too slow.

Space

O(n), where n is the length of `nums`. This is for storing a copy of the `nums` array for each simulation.

Trade-offs

Pros

Simple to understand and implement as it follows the problem description literally.
Correct for the given constraints if the execution time is within the limits.

Cons

The time complexity can be high if the sum of elements in nums is large and there are many zero-crossings, potentially leading to a Time Limit Exceeded error on larger test cases.

Solutions

Solution

1class Solution {2public3  int countValidSelections(int[] nums) {4    int s = Arrays.stream(nums).sum();5    int ans = 0, l = 0;6    for (int x : nums) {7      if (x != 0) {8        l += x;9      } else if (l * 2 == s) {10        ans += 2;11      } else if (Math.abs(l * 2 - s) <= 1) {12        ++ans;13      }14    }15    return ans;16  }17}

1class Solution:2    def countValidSelections(self, nums: List[int]) -> int: s = sum(nums) ans = l = 0 for x in nums: if x: l += x elif l * 2 == s: ans += 2 elif abs(l * 2 - s) == 1: ans += 1 return ans

1class Solution {2public:3  int countValidSelections(vector<int> &nums) {4    int s = accumulate(nums.begin(), nums.end(), 0);5    int ans = 0, l = 0;6    for (int x : nums) {7      if (x) {8        l += x;9      } else if (l * 2 == s) {10        ans += 2;11      } else if (abs(l * 2 - s) <= 1) {12        ++ans;13      }14    }15    return ans;16  }17};

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem