Scale Engineer

Ant on the Boundary

Easy
#2696Time: 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.1 company
Patterns
Prefix Sum
Data structures
Array
Companies
Accenture

Prompt

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

3 approaches with complexity analysis and trade-offs.

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.

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.

Walkthrough

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.

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;    }}

Complexity

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.

Trade-offs

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.

Solutions

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

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem