Make Array Elements Equal to Zero - Practice Coding Problems

Make Array Elements Equal to Zero - 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.

Input & Output

Example 1 — Basic Case

$ Input: nums = [3,0,1,0,2]

› Output: 2

💡 Note: Start at index 1 going right, or start at index 3 going left. Both configurations can make all elements zero through the bouncing process.

Example 2 — Single Zero

$ Input: nums = [1,0,2]

› Output: 2

💡 Note: Can start at index 1 going either left or right. Both directions eventually make all elements zero.

Example 3 — No Valid Configurations

$ Input: nums = [1,2,3]

› Output: 0

💡 Note: No zero positions exist, so no valid starting configurations are possible.

Constraints

1 ≤ nums.length ≤ 2000
0 ≤ nums[i] ≤ 1000
At least one element in nums is 0

Visualization

Tap to expand

Understanding the Visualization

Input

Array with some zeros and positive integers

Process

Robot starts at zero, bounces and decrements positive values

Output

Count of valid starting configurations

Key Takeaway

🎯 Key Insight: Simulate each possible starting configuration to count how many lead to all zeros

Asked in

G Google 12 a Amazon 8 f Meta 5

The key insight is that we must simulate the bouncing robot process for each possible starting configuration. The robot starts at zero positions and bounces between positive elements, decrementing them. Best approach is simulation with O(n × s) time complexity where s is the sum of elements.

Common Approaches

Approach	Time	Space	Notes
✓ Simulation for Each Starting Configuration	O(n × s)	O(n)	Try every possible starting position and direction, simulate the entire process
Mathematical Pattern Recognition	O(n²)	O(1)	Use mathematical analysis to determine valid configurations without full simulation

Simulation for Each Starting Configuration — Algorithm Steps

Find all positions where nums[i] == 0
For each zero position, try both left and right directions
Simulate the movement process completely
Count valid configurations

Visualization

Tap to expand

Step-by-Step Walkthrough

Find Zeros

Identify all positions where nums[i] == 0

Try Directions

For each zero position, try both left and right

Simulate

Run the movement process and count valid configs

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

int solution(int* nums, int n) {
    int count = 0;
    
    // Try each position that has value 0
    for (int start = 0; start < n; start++) {
        if (nums[start] != 0) continue;
        
        // Try both directions: left (-1) and right (1)
        int directions[2] = {-1, 1};
        for (int d = 0; d < 2; d++) {
            int direction = directions[d];
            
            // Make a copy to simulate
            int* temp = (int*)malloc(n * sizeof(int));
            memcpy(temp, nums, n * sizeof(int));
            
            int curr = start;
            int currDir = direction;
            
            int sum = 0;
            for (int i = 0; i < n; i++) sum += temp[i];
            int maxSteps = sum * 2 + n;
            int steps = 0;
            
            while (steps < maxSteps) {
                steps++;
                
                // Check bounds
                if (curr < 0 || curr >= n) break;
                
                // If current position is 0, just move
                if (temp[curr] == 0) {
                    curr += currDir;
                } else {
                    // Decrement, reverse direction, then move
                    temp[curr]--;
                    currDir = -currDir;
                    curr += currDir;
                }
            }
            
            // Check if all elements are 0
            bool allZero = true;
            for (int i = 0; i < n; i++) {
                if (temp[i] != 0) {
                    allZero = false;
                    break;
                }
            }
            
            if (allZero) count++;
            free(temp);
        }
    }
    
    return count;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    // Parse array format [1,2,3]
    int nums[1000];
    int n = 0;
    char* token = strtok(line, "[,]");
    while (token != NULL) {
        if (strlen(token) > 0 && token[0] >= '0' && token[0] <= '9') {
            nums[n++] = atoi(token);
        }
        token = strtok(NULL, "[,]");
    }
    
    int result = solution(nums, n);
    printf("%d\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n × s)

For each zero position (up to n), simulate the process which can take up to s steps where s is the sum of all elements

✓ Linear Growth

Space Complexity

O(n)

Need to create a copy of the array for each simulation

⚡ Linearithmic Space

12.5K Views

Medium Frequency

~15 min Avg. Time

234 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Simulation for Each Starting Configuration — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler