Make Array Elements Equal to Zero

main.md

Question

Approach

I start by identifying all indices where nums[i] == 0 — these are the possible starting positions. For each such index, I simulate the described process twice: once moving left and once moving right. During the simulation, I maintain a copy of the array so I can decrement values and reverse direction as required. If I exit the bounds of the array and all elements are 0, that starting position and direction count as a valid selection. I sum up all valid cases and return that count.

Implementation

class Solution:
    def countValidSelections(self, nums: List[int]) -> int:
        def simulate(start: int, direction: int) -> bool:
            arr = nums[:]
            curr = start
            n = len(arr)
            while 0 <= curr < n:
                if arr[curr] == 0:
                    curr += direction
                else:
                    arr[curr] -= 1
                    direction *= -1
                    curr += direction
            return all(x == 0 for x in arr)

        count = 0
        for i, val in enumerate(nums):
            if val == 0:
                if simulate(i, -1):
                    count += 1
                if simulate(i, 1):
                    count += 1
        return count

Complexities

• Time: O(k * n^2)
• Space: O(n)