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.

Examples

Example 1:

1
2
3
4
5
6


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:

1
2
3
4
5
6
7


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] <= 10
nums[i] != 0

Solution

Method 1 – Prefix Sum Simulation

Intuition

The ant’s position after each move is the sum of all previous moves. If the position becomes zero after any move, the ant is back on the boundary. We can track the position step by step and count how many times it returns to zero.

Approach

Initialize a variable pos to 0 to track the ant’s current position.
Initialize a counter ans to 0 for the number of returns to the boundary.
Iterate through each value in nums:

Add the current value to pos.
If pos is 0, increment ans.

Return ans after processing all moves.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11


class Solution {
public:
   int returnToBoundaryCount(vector<int>& nums) {
      int pos = 0, ans = 0;
      for (int n : nums) {
        pos += n;
        if (pos == 0) ans++;
      }
      return ans;
   }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12


type Solution struct{}

func (Solution) ReturnToBoundaryCount(nums []int) int {
   pos, ans := 0, 0
   for _, n := range nums {
      pos += n
      if pos == 0 {
        ans++
      }
   }
   return ans
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10


class Solution {
   public int returnToBoundaryCount(int[] nums) {
      int pos = 0, ans = 0;
      for (int n : nums) {
        pos += n;
        if (pos == 0) ans++;
      }
      return ans;
   }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11


class Solution {
   fun returnToBoundaryCount(nums: IntArray): Int {
      var pos = 0
      var ans = 0
      for (n in nums) {
        pos += n
        if (pos == 0) ans++
      }
      return ans
   }
}

1
2
3
4
5
6
7
8
9


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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12


impl Solution {
   pub fn return_to_boundary_count(nums: Vec<i32>) -> i32 {
      let (mut pos, mut ans) = (0, 0);
      for n in nums {
        pos += n;
        if pos == 0 {
           ans += 1;
        }
      }
      ans
   }
}

Complexity

⏰ Time complexity: O(N), where N is the length of nums.
🧺 Space complexity: O(1), only constant extra space is used.

Problem#

Examples#

Solution#

Method 1 – Prefix Sum Simulation#

Intuition#

Approach#

Code#

Complexity#