LeetCode 3354 - Make Array Elements Equal to Zero

The problem gives us an integer array nums, where some elements may already be zero and others are positive integers. We must choose a starting index curr such that nums[curr] == 0, and also choose an initial movement direction, either left or right.

leetcodeeasyarraysimulationprefix-sum

LeetCode Problem 3354

Difficulty: 🟢 Easy
Topics: Array, Simulation, Prefix Sum

Solution

Problem Understanding

The problem gives us an integer array nums, where some elements may already be zero and others are positive integers. We must choose a starting index curr such that nums[curr] == 0, and also choose an initial movement direction, either left or right.

Once the process begins, we repeatedly follow a set of movement rules until the pointer moves outside the array boundaries.

If the current position contains 0, we simply continue moving in the current direction. If the current position contains a positive value, we decrement that value by 1, reverse direction, and then move one step in the new direction.

A starting configuration is considered valid if, after the simulation ends, every element in the array has become zero.

The task is to count how many valid (starting_index, direction) choices exist.

The important detail is that we are only allowed to start on indices where the value is already zero. For each such index, we may try both directions independently.

The constraints are relatively small:

  • 1 <= nums.length <= 100
  • 0 <= nums[i] <= 100

Because the array size is tiny, a direct simulation approach is completely feasible. Even if we simulate every possible starting state, the total work remains manageable.

There are several edge cases worth noticing early:

  • Arrays containing only zeros. In this case, every zero index with both directions may be valid.
  • Arrays with exactly one zero.
  • Arrays where positive values exist only on one side of the starting point.
  • Cases where the simulation exits the array before all numbers become zero.
  • Cases where the pointer repeatedly bounces between elements.

The problem guarantees that at least one zero exists, so there is always at least one possible starting position to test.

Approaches

Brute Force Simulation

The most direct solution is to try every valid starting configuration.

For each index i where nums[i] == 0, we try:

  • moving left initially
  • moving right initially

For each attempt, we simulate the process exactly as described in the statement.

During simulation:

  • If we land on zero, we continue in the same direction.
  • If we land on a positive value, we decrement it, reverse direction, and move.

Eventually the pointer exits the array. At that moment, we check whether all values have become zero. If yes, the starting configuration is valid.

This approach is guaranteed to be correct because it follows the rules literally. Since the constraints are very small, even repeated simulations are fast enough.

Key Insight

Although the problem mentions prefix sums as a topic, the simplest and most reliable solution is straightforward simulation.

The main observation is that the state space is extremely small:

  • At most 100 indices
  • At most 2 directions
  • Each element decreases only a limited number of times

Every decrement reduces the total array sum by 1, so the process cannot continue forever. Once all decrements are exhausted, the pointer eventually leaves the array.

Because of this bounded behavior, brute force simulation is already optimal enough for the constraints.

Approach Time Complexity Space Complexity Notes
Brute Force O(n² × S) O(n) Simulate every valid start, where S is total sum of array
Optimal O(n² × S) O(n) Same simulation approach, already efficient enough for constraints

Here:

  • n is the array length
  • S is the sum of all elements in nums

Since n <= 100 and S <= 10000, this runs comfortably within limits.

Algorithm Walkthrough

  1. Initialize a variable answer = 0 to count valid selections.
  2. Iterate through every index i in the array.
  3. Skip indices where nums[i] != 0, because the rules only allow starting from zero-valued positions.
  4. For each valid zero index, test both possible directions:
  • -1 for left
  • +1 for right
  1. For each attempt:

  • Create a copy of the array because the simulation mutates values.

  • Set:

  • curr = i

  • direction = initial_direction

  1. Start simulating while curr remains inside the array bounds.
  2. At each step:

  • If arr[curr] == 0:

  • Move directly using the current direction.

  • Otherwise:

  • Decrement arr[curr]

  • Reverse direction

  • Move one step in the new direction

  1. When the pointer leaves the array, check whether all values are now zero.
  2. If every value is zero, increment answer.
  3. After testing all starting states, return answer.

Why it works

Each simulation exactly follows the rules given in the problem statement. Every time we encounter a positive value, we reduce the total array sum by one. Since the total sum is finite and never increases, the process must eventually terminate.

A starting configuration is counted only if the final array contains all zeros, which matches the problem definition precisely. Because we test every allowed starting state independently, the algorithm finds all valid selections and no invalid ones.

Python Solution

from typing import List

class Solution:
    def countValidSelections(self, nums: List[int]) -> int:
        def is_valid(start: int, direction: int) -> bool:
            arr = nums[:]
            curr = start
            move = direction

            while 0 <= curr < len(arr):
                if arr[curr] == 0:
                    curr += move
                else:
                    arr[curr] -= 1
                    move *= -1
                    curr += move

            return all(value == 0 for value in arr)

        answer = 0

        for i, value in enumerate(nums):
            if value == 0:
                if is_valid(i, -1):
                    answer += 1

                if is_valid(i, 1):
                    answer += 1

        return answer

The implementation closely mirrors the algorithm description.

The helper function is_valid performs one complete simulation for a given starting index and direction. Since the simulation modifies array values, we first create a copy using nums[:].

The variable curr tracks the current position, while move stores the current direction. We use:

  • -1 for left
  • 1 for right

Inside the simulation loop:

  • If the current value is zero, we continue moving normally.
  • Otherwise, we decrement the value, reverse direction using move *= -1, and then move.

After the pointer exits the array, we verify whether every element became zero using all(...).

The outer loop tests every zero-valued index with both directions and counts how many simulations succeed.

Go Solution

func countValidSelections(nums []int) int {
	n := len(nums)

	isValid := func(start int, direction int) bool {
		arr := make([]int, n)
		copy(arr, nums)

		curr := start
		move := direction

		for curr >= 0 && curr < n {
			if arr[curr] == 0 {
				curr += move
			} else {
				arr[curr]--
				move *= -1
				curr += move
			}
		}

		for _, value := range arr {
			if value != 0 {
				return false
			}
		}

		return true
	}

	answer := 0

	for i, value := range nums {
		if value == 0 {
			if isValid(i, -1) {
				answer++
			}

			if isValid(i, 1) {
				answer++
			}
		}
	}

	return answer
}

The Go implementation follows the same logic as the Python version.

Since slices are reference-like structures in Go, we must explicitly create a copied slice using make and copy before simulation. Otherwise, modifications would affect the original array across different tests.

Go integers are fully sufficient here because the constraints are tiny, so integer overflow is not a concern.

Worked Examples

Example 1

Input:

nums = [1,0,2,0,3]

Valid zero positions are:

  • index 1
  • index 3

We test both directions for each.

Start at index 3, move left

Step curr direction Array State
Initial 3 Left [1,0,2,0,3]
Move left through zero 2 Left [1,0,2,0,3]
Decrement index 2 3 Right [1,0,1,0,3]
Move right through zero 4 Right [1,0,1,0,3]
Decrement index 4 3 Left [1,0,1,0,2]
Move left through zero 2 Left [1,0,1,0,2]
Decrement index 2 3 Right [1,0,0,0,2]
Continue process ... ... ...
Final خارج array - [0,0,0,0,0]

This selection is valid.

Start at index 3, move right

The same bouncing behavior eventually reduces all elements to zero.

This selection is also valid.

Other starting states

All other configurations fail because the pointer exits before clearing every positive value.

Final answer:

2

Example 2

Input:

nums = [2,3,4,0,4,1,0]

Possible starting positions:

  • index 3
  • index 6

Testing all four direction choices eventually leaves some positive numbers unchanged.

For example:

  • starting at index 6 and moving right exits immediately
  • starting at index 3 cannot fully clear both sides before termination

Final answer:

0

Complexity Analysis

Measure Complexity Explanation
Time O(n² × S) Up to 2n simulations, each performing at most proportional work to total decrements
Space O(n) Array copy used during simulation

The simulation cost is bounded because every decrement reduces the total sum by one. Once all decrements are exhausted, the pointer can only move across zeros until it exits the array. Therefore each simulation remains finite and efficient for the given constraints.

Test Cases

sol = Solution()

# Provided examples
assert sol.countValidSelections([1, 0, 2, 0, 3]) == 2  # example 1
assert sol.countValidSelections([2, 3, 4, 0, 4, 1, 0]) == 0  # example 2

# Single zero element
assert sol.countValidSelections([0]) == 2  # both directions valid

# All zeros
assert sol.countValidSelections([0, 0, 0]) == 6  # every start and direction works

# One positive next to zero
assert sol.countValidSelections([1, 0]) == 1  # only moving left works

# Symmetric simple case
assert sol.countValidSelections([1, 0, 1]) == 2  # both directions valid

# No valid configurations
assert sol.countValidSelections([5, 0, 1]) == 0  # cannot clear everything

# Multiple zeros
assert sol.countValidSelections([0, 2, 0]) == 0  # exits too early

# Larger balanced case
assert sol.countValidSelections([2, 0, 2]) == 2  # both directions valid from center

# Zero at boundary
assert sol.countValidSelections([0, 1, 1]) == 0  # exits immediately on one side

# Complex bouncing behavior
assert sol.countValidSelections([1, 0, 3, 0, 1]) == 0  # cannot fully clear
Test Why
[1,0,2,0,3] Verifies the main example
[2,3,4,0,4,1,0] Verifies no valid solutions
[0] Smallest possible array
[0,0,0] Every configuration should succeed
[1,0] Tests boundary movement
[1,0,1] Simple symmetric bouncing
[5,0,1] Large imbalance case
[0,2,0] Multiple zeros but invalid
[2,0,2] Balanced reductions
[0,1,1] Zero at array edge
[1,0,3,0,1] Longer simulation path

Edge Cases

One important edge case is an array containing only zeros. In this scenario, the pointer never performs any decrements because every position already contains zero. Regardless of the chosen starting index or direction, the pointer eventually exits the array while the array remains entirely zero. The implementation handles this naturally because the simulation simply walks out of bounds and the final all(...) check succeeds.

Another tricky case occurs when the starting zero lies at the boundary of the array. For example, in [0,1,1], moving left immediately exits the array. A buggy implementation might incorrectly count this as valid without checking remaining values. The solution correctly verifies the final array state after simulation, so unfinished positive values prevent false positives.

A third important case involves repeated bouncing between positions. Arrays like [2,0,2] force the pointer to alternate directions many times. An incorrect implementation might forget to reverse direction after decrementing or might move before changing direction. The simulation strictly follows the required order:

  1. decrement
  2. reverse direction
  3. move

This guarantees correct behavior even in long bouncing sequences.