Ant on the Boundary - Practice Coding Problems

Ant on the Boundary - Problem

An ant is on a boundary. It sometimes goes left and sometimes right. You are given an array of non-zero integers nums. The ant starts reading nums from the first element of it to its end.

At each step, it moves according to the value of the current element:

If nums[i] < 0, it moves left by -nums[i] units.
If nums[i] > 0, it moves right by nums[i] units.

Return the number of times the ant returns to the boundary.

Notes:

There is an infinite space on both sides of the boundary.
We check whether the ant is on the boundary only after it has moved |nums[i]| units. In other words, if the ant crosses the boundary during its movement, it does not count.

Input & Output

Example 1 — Basic Movement

$ Input: nums = [2,-3,3,-4]

› Output: 0

💡 Note: Ant moves: start(0) → +2(2) → -3(-1) → +3(2) → -4(-2). Never returns to position 0.

Example 2 — Return to Boundary

$ Input: nums = [3,-3,4,-4]

› Output: 2

💡 Note: Ant moves: start(0) → +3(3) → -3(0) → +4(4) → -4(0). Returns to boundary twice.

Example 3 — No Returns

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

› Output: 0

💡 Note: Ant moves: start(0) → +1(1) → +2(3) → +3(6). Always moving right, never returns to 0.

Constraints

1 ≤ nums.length ≤ 50
-100 ≤ nums[i] ≤ 100
nums[i] ≠ 0

Visualization

Tap to expand

Understanding the Visualization

Input

Array of movement values (positive = right, negative = left)

Process

Track cumulative position after each move

Output

Count times position equals 0 (boundary)

Key Takeaway

🎯 Key Insight: Count when cumulative sum equals zero

Asked in

G Google 15 a Amazon 12

The key insight is that the ant returns to the boundary whenever the cumulative sum of movements equals zero. Best approach uses prefix sum to track position. Time: O(n), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Prefix Sum	O(n)	O(1)	Use running sum to track position and count zero crossings
Brute Force Simulation	O(n)	O(1)	Track ant's position step by step and count boundary returns

Prefix Sum — Algorithm Steps

Initialize running sum and counter
Add each movement to running sum
Count occurrences where running sum equals zero

Visualization

Tap to expand

Step-by-Step Walkthrough

Initialize

Start with prefix sum = 0

Accumulate

Add each number to running total

Check Zeros

Count when prefix sum equals 0

Code -

solution.c — C

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

int solution(int* nums, int numsSize) {
    int prefixSum = 0;
    int count = 0;
    
    for (int i = 0; i < numsSize; i++) {
        prefixSum += nums[i];
        if (prefixSum == 0) {
            count++;
        }
    }
    
    return count;
}

int main() {
    char line[1000];
    fgets(line, sizeof(line), stdin);
    
    // Simple parsing for [1,2,3] format
    int nums[1000];
    int size = 0;
    char* token = strtok(line + 1, ",]");
    
    while (token != NULL) {
        nums[size++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    printf("%d\n", solution(nums, size));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Single iteration through the array

✓ Linear Growth

Space Complexity

O(1)

Only storing running sum and counter variables

✓ Linear Space

5.4K Views

Medium Frequency

~10 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

Prefix Sum — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler