Make Array Elements Equal to Zero
EasyUpdated: Aug 2, 2025
Practice on:
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
curris out of the range[0, n - 1], this process ends. - If
nums[curr] == 0, move in the current direction by incrementingcurrif you are moving right, or decrementingcurrif 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.
Examples
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,2,**_0_** ,2] -> [1,0,**_2_** ,0,2] -> [1,0,1,**_0_** ,2] -> [1,0,1,0,**_3_**] -> [1,0,1,**_0_** ,2] -> [1,0,**_1_** ,0,2] -> [1,0,0,**_0_** ,2] -> [1,0,0,0,**_3_**] -> [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 <= 1000 <= nums[i] <= 100- There is at least one element
iwherenums[i] == 0.
Solution
Method 1 – Simulation with Backtracking
Intuition
We need to count all valid ways to select a starting position (where nums[curr] == 0) and a direction (left or right) such that, following the process, all elements become zero. Since the array is small (as per constraints), we can simulate the process for each possible starting position and direction.
Approach
- For each index where
nums[i] == 0, try both directions (left and right). - For each (start, direction), simulate the process:
- Move as per the rules, flipping direction and decrementing as needed.
- Track visited states to avoid infinite loops.
- If all elements are zero at the end, count this as a valid selection.
- Return the total count of valid selections.
Code
C++
class Solution {
public:
int countValidSelections(vector<int>& nums) {
int n = nums.size(), ans = 0;
for (int i = 0; i < n; ++i) {
if (nums[i] != 0) continue;
for (int dir : {-1, 1}) {
vector<int> arr = nums;
int cur = i, d = dir;
while (cur >= 0 && cur < n) {
if (arr[cur] == 0) cur += d;
else {
arr[cur]--;
d = -d;
cur += d;
}
}
if (all_of(arr.begin(), arr.end(), [](int x){return x==0;})) ans++;
}
}
return ans;
}
};
Go
func countValidSelections(nums []int) int {
n, ans := len(nums), 0
for i := 0; i < n; i++ {
if nums[i] != 0 {
continue
}
for _, dir := range []int{-1, 1} {
arr := append([]int(nil), nums...)
cur, d := i, dir
for cur >= 0 && cur < n {
if arr[cur] == 0 {
cur += d
} else {
arr[cur]--
d = -d
cur += d
}
}
ok := true
for _, x := range arr {
if x != 0 {
ok = false
break
}
}
if ok {
ans++
}
}
}
return ans
}
Java
class Solution {
public int countValidSelections(int[] nums) {
int n = nums.length, ans = 0;
for (int i = 0; i < n; ++i) {
if (nums[i] != 0) continue;
for (int dir : new int[]{-1, 1}) {
int[] arr = nums.clone();
int cur = i, d = dir;
while (cur >= 0 && cur < n) {
if (arr[cur] == 0) cur += d;
else {
arr[cur]--;
d = -d;
cur += d;
}
}
boolean ok = true;
for (int x : arr) if (x != 0) ok = false;
if (ok) ans++;
}
}
return ans;
}
}
Kotlin
class Solution {
fun countValidSelections(nums: IntArray): Int {
val n = nums.size
var ans = 0
for (i in 0 until n) {
if (nums[i] != 0) continue
for (dir in listOf(-1, 1)) {
val arr = nums.copyOf()
var cur = i
var d = dir
while (cur in 0 until n) {
if (arr[cur] == 0) cur += d
else {
arr[cur]--
d = -d
cur += d
}
}
if (arr.all { it == 0 }) ans++
}
}
return ans
}
}
Python
class Solution:
def countValidSelections(self, nums: list[int]) -> int:
n = len(nums)
ans = 0
for i in range(n):
if nums[i] != 0:
continue
for d in [-1, 1]:
arr = nums[:]
cur = i
dir = d
while 0 <= cur < n:
if arr[cur] == 0:
cur += dir
else:
arr[cur] -= 1
dir = -dir
cur += dir
if all(x == 0 for x in arr):
ans += 1
return ans
Rust
impl Solution {
pub fn count_valid_selections(nums: Vec<i32>) -> i32 {
let n = nums.len();
let mut ans = 0;
for i in 0..n {
if nums[i] != 0 { continue; }
for &dir in &[-1, 1] {
let mut arr = nums.clone();
let mut cur = i as i32;
let mut d = dir;
while cur >= 0 && cur < n as i32 {
let idx = cur as usize;
if arr[idx] == 0 {
cur += d;
} else {
arr[idx] -= 1;
d = -d;
cur += d;
}
}
if arr.iter().all(|&x| x == 0) {
ans += 1;
}
}
}
ans
}
}
TypeScript
class Solution {
countValidSelections(nums: number[]): number {
const n = nums.length;
let ans = 0;
for (let i = 0; i < n; ++i) {
if (nums[i] !== 0) continue;
for (const dir of [-1, 1]) {
const arr = nums.slice();
let cur = i, d = dir;
while (cur >= 0 && cur < n) {
if (arr[cur] === 0) cur += d;
else {
arr[cur]--;
d = -d;
cur += d;
}
}
if (arr.every(x => x === 0)) ans++;
}
}
return ans;
}
}
Complexity
- ⏰ Time complexity:
O(n^2), as for each position and direction we may visit all elements. - 🧺 Space complexity:
O(n), for the array copy in each simulation.