Circular Array Loop

Circular Array Loop

What is this problem about?

You are given an array of integers where each element represents the number of steps to move forward (if positive) or backward (if negative). Since the array is "circular," moving past the end brings you back to the beginning. You need to find if there is a cycle in the array of length $> 1$ where all movements in the cycle are in the same direction (all positive or all negative).

Why is this asked in interviews?

Goldman Sachs and Microsoft use this to test your proficiency with the "Slow and Fast Pointers" (Tortoise and Hare) algorithm. It’s a variation of the cycle detection problem in a linked list but with added constraints (same direction, length $> 1$). It evaluations your ability to handle modular arithmetic and complex state transitions.

Algorithmic pattern used

This problem uses the Two Pointers (Slow/Fast) pattern for cycle detection. For each index that hasn't been visited, you start a slow pointer (moves 1 step) and a fast pointer (moves 2 steps). If they meet, a cycle exists. You must also check that the cycle length is greater than 1 (a node doesn't point to itself) and that every node in the cycle has the same sign as the starting node.

Example explanation

Array: [2, -1, 1, 2, 2]

1. Start at index 0 (val 2).
2. Move 2 steps: index 0 -> 2 -> 3 -> 0... (Cycle found!)
3. All steps are positive? Yes (2, 1, 2).
4. Cycle length > 1? Yes. Result: True. If array was [-1, 2], index 0 points to index 1, and index 1 points back to 0. But 0 is negative and 1 is positive. Not a valid cycle.

Common mistakes candidates make

The most common mistake is forgetting the "same direction" rule. Another is failing to handle the "cycle of length 1" case (e.g., an element n where (i + nums[i]) % n == i). Candidates also struggle with the modulo operator for negative numbers; in many languages, -1 % 5 is -1, but for circular arrays, it should be 4.

Interview preparation tip

Master the "Slow/Fast Pointers" pattern. It's the standard way to detect cycles in any structure that can be modeled as a directed graph where each node has exactly one outgoing edge.