Editorial

Solution walkthrough

Review the explanation, then compare the reference implementation.

Video explanation

Solution

Intuition

Starting from a zero, each encounter with a positive value removes one unit and reverses direction. Consequently, decrements alternate between the left and right sides of the starting position. To empty both sides before leaving the array, their total values must be equal or differ by exactly one.

Approach

Build prefix and suffix sums. For every zero position, compare the two sums there; including the starting value changes nothing because it is zero. If the sums are equal, either initial direction works, so add two. If they differ by one, only the direction toward the larger sum works, so add one. Otherwise add nothing.

With equal totals, alternating removals exhaust both sides together. With a difference of one, starting toward the larger side gives it both the first and last removal. A larger imbalance leaves positive values behind when the walk exits. This counts valid starts and directions without simulating individual decrements.

class Solution:
    def countValidSelections(self, nums: List[int]) -> int:
        n = len(nums)
        pr = [nums[0]] * n
        su = [nums[-1]] * n

        for i in range(1, n):
            pr[i] = pr[i - 1] + nums[i]

        for i in range(n - 2, -1, -1):
            su[i] = su[i + 1] + nums[i]

        res = 0

        for i in range(n):
            if nums[i] == 0:
                if pr[i] == su[i]:
                    res += 2
                elif abs(pr[i] - su[i]) == 1:
                    res += 1

        return res

Complexity analysis

Let n = nums.length. Time: O(n). Auxiliary space: O(n) for prefix and suffix sums.