# Ant on the Boundary
**Difficulty:** EASY
[External](https://leetcode.com/problems/ant-on-the-boundary)
Canonical: https://scaleengineer.com/dsa/problems/ant-on-the-boundary
**Patterns:** [Prefix Sum](https://scaleengineer.com/dsa/patterns/prefix-sum)
**Data structures:** Array
**Companies:** [Accenture](https://scaleengineer.com/companies/accenture)
---
## 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.

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

# Approaches
## Brute Force with Nested Loops
This approach simulates the ant's movement by recalculating its position from the start for each step. It uses nested loops. The outer loop iterates through each move, and for each move, the inner loop calculates the ant's position by summing up all movements from the beginning up to the current move.
**Time:** O(N^2) - Where N is the number of elements in `nums`. The nested loops lead to a quadratic time complexity. The outer loop runs N times, and the inner loop runs up to N times for each outer iteration. · **Space:** O(1) - We only use a few variables to store the counter and the current position, which does not depend on the input size.
**Pros:** Simple to understand and implement directly from the problem definition.; Uses constant extra space.
**Cons:** Highly inefficient due to O(N^2) time complexity.; Performs many redundant calculations by re-computing the prefix sum for each element.
### Explanation
The brute-force method directly translates the problem statement into a straightforward, albeit inefficient, algorithm. We want to know the ant's position after each move. So, for the first move, we take `nums[0]`. For the second move, we calculate `nums[0] + nums[1]`. For the k-th move, we calculate the sum of `nums[0]` through `nums[k-1]`. This approach does exactly that. It iterates from the first move to the last. For each move `i`, it calculates the sum of all numbers from the start of the array up to index `i`. If this sum is zero, it means the ant is back at the boundary, and we increment a counter. This process is repeated for all moves.

```java
class Solution {
    public int returnToBoundaryCount(int[] nums) {
        int boundaryReturns = 0;
        for (int i = 0; i < nums.length; i++) {
            long currentPosition = 0;
            // Inner loop to calculate position from the start
            for (int j = 0; j <= i; j++) {
                currentPosition += nums[j];
            }
            if (currentPosition == 0) {
                boundaryReturns++;
            }
        }
        return boundaryReturns;
    }
}
```
### Algorithm
- Initialize a counter `boundaryReturns` to 0.
- Iterate through the `nums` array with an index `i` from 0 to `nums.length - 1`.
- For each `i`, start an inner loop with index `j` from 0 to `i` to calculate the cumulative sum.
- Maintain a `currentPosition` variable, initialized to 0 before the inner loop.
- In the inner loop, add `nums[j]` to `currentPosition`.
- After the inner loop, if `currentPosition` is 0, increment `boundaryReturns`.
- After the outer loop finishes, return `boundaryReturns`.

## Two-Pass Simulation with Auxiliary Space
This approach improves upon the brute-force method by avoiding recalculations. In a first pass, it computes the ant's position after each move and stores these positions in an auxiliary array. In a second pass, it iterates through this new array to count how many times the position was 0.
**Time:** O(N) - We perform two separate, non-nested loops over the N elements. The total time is O(N) + O(N), which simplifies to O(N). · **Space:** O(N) - An auxiliary list of size N is used to store the position of the ant after each move.
**Pros:** Improves time complexity to a linear O(N).; Separates the logic of position calculation and counting, which can be clean in some contexts.
**Cons:** Uses O(N) extra space, which is not optimal for this problem.
### Explanation
To avoid the O(N^2) complexity, we can observe that the position at step `i` is simply the position at step `i-1` plus the move `nums[i]`. This suggests we can calculate all positions sequentially in one pass. This approach does so by iterating through `nums`, calculating the cumulative sum at each step, and storing these cumulative sums (positions) in a separate list. Once all positions are calculated and stored, a second loop iterates through the list of positions to count how many times the value is 0. This separates the calculation of positions from the counting of boundary returns.

```java
import java.util.ArrayList;
import java.util.List;

class Solution {
    public int returnToBoundaryCount(int[] nums) {
        long currentPosition = 0;
        List<Long> positions = new ArrayList<>();
        
        // First pass: calculate and store all positions
        for (int num : nums) {
            currentPosition += num;
            positions.add(currentPosition);
        }
        
        // Second pass: count boundary returns
        int boundaryReturns = 0;
        for (long pos : positions) {
            if (pos == 0) {
                boundaryReturns++;
            }
        }
        
        return boundaryReturns;
    }
}
```
### Algorithm
- Initialize `currentPosition = 0`.
- Initialize an auxiliary list, `positions`.
- **First Pass:** Iterate through the `nums` array.
  - For each `num`, update `currentPosition += num`.
  - Add the new `currentPosition` to the `positions` list.
- Initialize `boundaryReturns = 0`.
- **Second Pass:** Iterate through the `positions` list.
  - If a stored position is 0, increment `boundaryReturns`.
- Return `boundaryReturns`.

## Single-Pass Simulation (Optimal)
This is the most efficient approach. It simulates the ant's movement in a single pass through the input array. It maintains a running sum of the ant's position and checks if it has returned to the boundary after each move, all within one loop.
**Time:** O(N) - It requires only a single pass through the `nums` array, making it very efficient. · **Space:** O(1) - It uses a constant amount of extra space for a few variables (`currentPosition`, `boundaryReturns`), regardless of the input size.
**Pros:** Optimal time complexity of O(N).; Optimal space complexity of O(1).; Simple, concise, and easy to understand.
**Cons:** There are no significant cons for this approach; it is optimal for this problem.
### Explanation
This optimal solution realizes that we don't need to store all the intermediate positions. We can check for a boundary return immediately after each move. We use a single variable, `currentPosition`, to keep track of the ant's location relative to the boundary (0). We iterate through the `nums` array just once. In each iteration, we update `currentPosition` with the current move. Immediately after updating, we check if `currentPosition` has become 0. If it has, we increment our `boundaryReturns` counter. This way, we combine the position calculation and the boundary check into a single, efficient step.

```java
class Solution {
    public int returnToBoundaryCount(int[] nums) {
        int boundaryReturns = 0;
        long currentPosition = 0;
        
        for (int num : nums) {
            currentPosition += num;
            if (currentPosition == 0) {
                boundaryReturns++;
            }
        }
        
        return boundaryReturns;
    }
}
```
### Algorithm
- Initialize `currentPosition = 0`.
- Initialize `boundaryReturns = 0`.
- Iterate through each number `num` in the `nums` array.
  - Update the position: `currentPosition += num`.
  - Check if the new position is the boundary: `if (currentPosition == 0)`.
  - If it is, increment `boundaryReturns`.
- After the loop, return `boundaryReturns`.

# Solutions
### Java

```java
class Solution {
public
  int returnToBoundaryCount(int[] nums) {
    int ans = 0, s = 0;
    for (int x : nums) {
      s += x;
      if (s == 0) {
        ++ans;
      }
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int returnToBoundaryCount(vector<int> &nums) {
    int ans = 0, s = 0;
    for (int x : nums) {
      s += x;
      ans += s == 0;
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def returnToBoundaryCount(
        self, nums: List[int]) -> int: return sum(s == 0 for s in accumulate(nums))

```