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:
nums[i] < 0, it moves left by -nums[i] units.nums[i] > 0, it moves right by nums[i] units.Return the number of times the ant returns to the boundary.
Notes:
|nums[i]| units. In other words, if the ant crosses the boundary during its movement, it does not count.
Example 1:
Input: nums = [2,3,-5] Output: 1 Explanation: After the first step, the ant is 2 steps to the right of the boundary. After the second step, the ant is 5 steps to the right of the boundary. After the third step, the ant is on the boundary. So the answer is 1.
Example 2:
Input: nums = [3,2,-3,-4] Output: 0 Explanation: After the first step, the ant is 3 steps to the right of the boundary. After the second step, the ant is 5 steps to the right of the boundary. After the third step, the ant is 2 steps to the right of the boundary. After the fourth step, the ant is 2 steps to the left of the boundary. The ant never returned to the boundary, so the answer is 0.
Constraints:
1 <= nums.length <= 100-10 <= nums[i] <= 10nums[i] != 0Problem Overview: An ant starts at position 0 on a number line. You receive an array nums where each value represents a movement. After applying each move sequentially, count how many times the ant lands exactly back on position 0.
Approach 1: Cumulative Position Tracking (O(n) time, O(1) space)
This approach directly simulates the ant’s movement using a running prefix sum. Start with a variable position = 0 and iterate through the array. For each step, add the move value to position. Every time position == 0, increment the answer counter. The key insight is that the ant’s location after each move is simply the cumulative sum of all previous moves. Since you only track a single integer and iterate once through the array, the solution runs in O(n) time with O(1) extra space. This pattern commonly appears in problems involving Prefix Sum and Simulation.
Approach 2: Pre-calculation of Positions (O(n) time, O(n) space)
Instead of updating a single running variable, this approach builds an explicit prefix array of positions. Create an array pos where pos[i] stores the ant’s position after the i-th move. Compute each entry using pos[i] = pos[i-1] + nums[i]. After constructing the prefix array, iterate through it and count how many values equal zero. This approach still runs in O(n) time but requires O(n) space to store intermediate positions. It can be useful if you need the full position history for debugging, visualization, or follow-up queries. The technique is a direct application of prefix accumulation on an Array.
Recommended for interviews: Cumulative Position Tracking. Interviewers expect you to recognize that the ant’s location is just a running prefix sum. The brute-style prefix array approach demonstrates understanding, but the constant-space simulation shows stronger problem-solving efficiency.
The simplest way to solve this problem is by keeping track of the ant's cumulative position as it traverses the nums array. At each step, we update the cumulative position based on the value of nums[i]. If this cumulative position becomes zero, it indicates that the ant has returned to the boundary.
We initialize position and returnCount to zero. For each element in the nums array, we update the current position by adding the value of the element. If the position becomes zero, we increment the returnCount. Finally, we return the count.
Time Complexity: O(n), where n is the number of elements in nums.
Space Complexity: O(1), as no additional data structures are used.
This approach involves calculating the position at every step in advance and checking if it has reached zero. Here, we maintain an array of positions to precompute the effect of each action on ant movement.
We maintain a positions array which is updated at each step. The ant's position changes based on additing the number from the nums array. Whenever a zero is found in the positions array except the initial position, we increment returnCount.
Time Complexity: O(n)
Space Complexity: O(n)
Based on the problem description, we only need to calculate how many zeros are in all prefix sums of nums.
The time complexity is O(n), where n is the length of nums. The space complexity is O(1).
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Approach 1: Cumulative Position Tracking | Time Complexity: O(n), where n is the number of elements in |
| Approach 2: Pre-calculation of Positions | Time Complexity: O(n) |
| Prefix Sum | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Cumulative Position Tracking | O(n) | O(1) | Best general solution. Minimal memory and simple single-pass logic. |
| Pre-calculation of Positions | O(n) | O(n) | Useful when you need the full history of positions for debugging or additional queries. |
LeetCode#3028 Ant on the Boundary - Python • CodeJulian • 1,344 views views
Watch 9 more video solutions →Practice Ant on the Boundary with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor