Ant on the Boundary

Difficulty: Easy | Acceptance: 74.40% | Paid: No Topics: Array, Simulation, Prefix Sum

An ant is sitting on the boundary of a number line. The ant starts at position 0. It is given an array nums of length n where nums[i] represents the move the ant makes at the i-th step.

If nums[i] > 0, the ant moves right nums[i] units. If nums[i] < 0, the ant moves left abs(nums[i]) units.

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

Note: The ant returns to the boundary when its position is 0 after a move. The ant does not count the starting position (0) as a return.

• Examples
• Constraints
• Brute Force Simulation
• Prefix Sum (Optimal)

Examples

Example 1:

Input: nums = [2,3,-5]
Output: 1
Explanation:
After the 1st move, the ant is at position 2.
After the 2nd move, the ant is at position 5.
After the 3rd move, the ant is at position 0.
So, the ant returns to the boundary 1 time.

Example 2:

Input: nums = [3,2,-3,-4]
Output: 0
Explanation:
After the 1st move, the ant is at position 3.
After the 2nd move, the ant is at position 5.
After the 3rd move, the ant is at position 2.
After the 4th move, the ant is at position -2.
The ant never returns to the boundary.

Constraints

1 <= nums.length <= 100
-10⁹ <= nums[i] <= 10⁹
nums[i] != 0

Brute Force Simulation

Intuition Simulate the ant’s movement step-by-step. For every step, calculate the total distance traveled from the start by summing all previous moves to check if the current position is 0.

Steps

• Initialize a counter for returns to 0.
• Iterate through the array with an outer loop representing the current step.
• Inside the outer loop, use an inner loop to sum all elements from the start up to the current index.
• If the calculated sum is 0, increment the counter.
• Return the counter.

class Solution:
    def returnToBoundaryCount(self, nums: list[int]) -> int:
        count = 0
        n = len(nums)
        for i in range(n):
            current_sum = 0
            for j in range(i + 1):
                current_sum += nums[j]
            if current_sum == 0:
                count += 1
        return count

Complexity

• Time: O(n²) - We iterate through the array and for each element, we sum up to that element again.
• Space: O(1) - We only use a few variables for counting and summing.
• Notes: This approach is inefficient for larger arrays but demonstrates the simulation logic clearly.

Prefix Sum (Optimal)

Intuition Instead of recalculating the sum from scratch for every step, maintain a running total (prefix sum) of the ant’s position. If the running total becomes 0, the ant is at the boundary.

Steps

• Initialize a variable position to 0 and a counter result to 0.
• Iterate through each number in the input array.
• Add the current number to position.
• If position is 0, increment result.
• Return result.

class Solution:
    def returnToBoundaryCount(self, nums: list[int]) -> int:
        position = 0
        count = 0
        for num in nums:
            position += num
            if position == 0:
                count += 1
        return count

Complexity

• Time: O(n) - We pass through the array exactly once.
• Space: O(1) - We only use two integer variables regardless of input size.
• Notes: This is the most efficient approach, utilizing the concept of a running prefix sum.