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.

Examples

Example 1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

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

1
2
3
4
5
6
7
8

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.

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

  1. For each index where nums[i] == 0, try both directions (left and right).
  2. 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.
  3. Return the total count of valid selections.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    int countWays(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;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
func countWays(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
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    public int countWays(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;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    fun countWays(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
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
    def countWays(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
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
impl Solution {
    pub fn count_ways(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
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    countWays(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.