Circular Array Loop

medium two pointers fast slow

Problem

Given a circular array where each cell is a signed offset, return whether the array contains a cycle of length > 1 that doesn't change direction.

Inputnums = [2,-1,1,2,2]

Outputtrue

0→2→3→0 is a positive cycle.

nums

def circular_array_loop(nums):
    n = len(nums)
    def nxt(i): return (i + nums[i]) % n
    for i in range(n):
        if nums[i] == 0: continue
        slow, fast = i, nxt(i)
        while nums[fast] * nums[i] > 0 and nums[nxt(fast)] * nums[i] > 0:
            if slow == fast:
                if slow == nxt(slow): break
                return True
            slow = nxt(slow); fast = nxt(nxt(fast))
    return False

function circularArrayLoop(nums) {
  const n = nums.length;
  const nxt = i => ((i + nums[i]) % n + n) % n;
  for (let i = 0; i < n; i++) {
    if (nums[i] === 0) continue;
    let slow = i, fast = nxt(i);
    while (nums[fast] * nums[i] > 0 && nums[nxt(fast)] * nums[i] > 0) {
      if (slow === fast) {
        if (slow === nxt(slow)) break;
        return true;
      }
      slow = nxt(slow); fast = nxt(nxt(fast));
    }
  }
  return false;
}

class Solution {
    public boolean circularArrayLoop(int[] nums) {
        int n = nums.length;
        for (int i = 0; i < n; i++) {
            if (nums[i] == 0) continue;
            int slow = i, fast = nxt(nums, i);
            while (nums[fast] * nums[i] > 0 && nums[nxt(nums, fast)] * nums[i] > 0) {
                if (slow == fast) { if (slow == nxt(nums, slow)) break; return true; }
                slow = nxt(nums, slow); fast = nxt(nums, nxt(nums, fast));
            }
        }
        return false;
    }
    int nxt(int[] nums, int i) {
        int n = nums.length;
        return ((i + nums[i]) % n + n) % n;
    }
}

class Solution {
    int nxt(vector& nums, int i) {
        int n = nums.size();
        return ((i + nums[i]) % n + n) % n;
    }
public:
    bool circularArrayLoop(vector& nums) {
        int n = nums.size();
        for (int i = 0; i < n; i++) {
            if (nums[i] == 0) continue;
            int slow = i, fast = nxt(nums, i);
            while (nums[fast] * (long)nums[i] > 0 && nums[nxt(nums, fast)] * (long)nums[i] > 0) {
                if (slow == fast) { if (slow == nxt(nums, slow)) break; return true; }
                slow = nxt(nums, slow); fast = nxt(nums, nxt(nums, fast));
            }
        }
        return false;
    }
};

Explanation

Each cell is a signed jump and we ask whether there is a valid cycle: it must stay in one direction (all moves positive or all negative) and have length greater than 1. We use fast and slow pointers to detect the loop.

The helper nxt(i) computes the next index, wrapping around with a modulo so the array behaves like a circle. From each start, slow moves one step and fast moves two.

Two guards keep the path valid. We require nums[fast] * nums[i] > 0 and the same for nxt(fast), which means the sign never flips — moving the same direction throughout. We also reject a one-element self-loop with the check slow == nxt(slow).

If slow ever equals fast while those guards hold, the two pointers met inside a real cycle and we return true. If a path breaks a guard, we try the next start.

Example: nums = [2, -1, 1, 2, 2]. Starting at index 0, the positive jumps trace 0 → 2 → 3 → 0, a directionally consistent cycle longer than one, so the answer is true.

Time: O(n) Space: O(1)