Circular Array Loop (LeetCode 457)

The problem

You get a circular array nums of non-zero integers. Standing on index i, you jump nums[i] steps: forward if positive, backward if negative, wrapping round the ends. Return True if there is a valid cycle: a loop of jumps that

• returns to where it started,
• has length greater than 1 (a single index jumping to itself does not count), and
• moves in one direction only (all values on the loop are positive, or all negative).

Input:  [2, -1, 1, 2, 2]
Output: True

From index 0, jump +2 to index 2, +1 to index 3, +2 (wrapping) to index 0. The loop 0 -> 2 -> 3 -> 0 has length 3 and all its values are positive.

How to think about it

Start with brute force. From every index, simulate jumps and record the indices you visit in a set. Stop if the sign changes. If you revisit an index, check whether that loop has more than one element. It works, but it needs O(n) extra space per start.

The key insight: each index has exactly one “next” index. nxt(i) = (i + nums[i]) % n. That makes the array a functional graph, a set of linked lists that all end in cycles. Finding a cycle in “follow next” is exactly what tortoise and hare does in O(1) space. Python’s % always returns a non-negative result, so backward jumps wrap correctly.

Then enforce the two extra rules. Direction: before every hare move, check that the node it stands on and the next node have the same sign as the start. If not, this start can’t produce a valid loop. Length: when the pointers meet, the meeting point is on the cycle. If nxt(s) == s, the cycle is a self-loop of length 1, which doesn’t count.

Which pattern is this? Fast & slow pointers on an implicit sequence. The tell is “following jumps through an array, does it loop?”

Approach

1. Define nxt(i) as (i + nums[i]) % n.
2. For each start i, record its direction pos = nums[i] > 0, and put s and f on i.
3. Loop: if f or nxt(f) has the wrong sign, give up on this start. Otherwise move s once and f twice.
4. If s == f, they met on the cycle. If it is a self-loop, give up on this start; otherwise return True.
5. If no start produced a valid cycle, return False.

Solution

def circular_array_loop(nums):
    n = len(nums)
    def nxt(i): return (i + nums[i]) % n            # Python % wraps negatives too
    for i in range(n):
        if nums[i] == 0: continue
        s = f = i; pos = nums[i] > 0                 # direction of this start
        while True:
            if (nums[f] > 0) != pos or (nums[nxt(f)] > 0) != pos: break   # direction changed
            f2 = nxt(nxt(f))
            if (nums[nxt(f)] > 0) != pos: break
            s = nxt(s); f = f2                       # tortoise 1, hare 2
            if s == f:
                if s == nxt(s): break                # self-loop: length 1 does not count
                return True
    return False
# circular_array_loop([2,-1,1,2,2]) -> True

The second sign check repeats part of the first and never fires on its own; it is harmless.

Dry run

On [2, -1, 1, 2, 2], starting from index 0 (pos = True):

It returns True. On [-1, -2, -3, -4, -5, 6] every negative start jumps to a positive value and breaks, and index 5 jumps to itself (a self-loop), so the answer is False.

Complexity

• Time: O(n²) worst case as written. Each start’s walk is O(n), and nothing is shared between starts, so a long path that ends in a sign change can be re-walked from every index on it. The standard fix for O(n) is to mark every index on a failed walk (for example, set it to 0, which the code already skips).
• Space: O(1). A few integer variables.

Edge cases and pitfalls

• Self-loops: [1] or any nums[i] that is a multiple of n jumps back to itself. That is a cycle of length 1, so it returns False.
• Mixed directions: [-2, 1, -1, -2, -2] has a loop only if you allow sign changes, so the answer is False.
• Two-element loops count: [1, 1] goes 0 -> 1 -> 0 and returns True.
• Negative modulo: in Java or C++, (i + nums[i]) % n can be negative. Use ((i + nums[i]) % n + n) % n there.
• Checking only the hare’s landing sign misses a sign change on the intermediate node it jumps over. Check both hops.

Related problems

• Linked List Cycle (LeetCode 141): the plain cycle check this builds on.
• Find the Duplicate Number (LeetCode 287): another array read as “index points to next index”.
• Happy Number (LeetCode 202): cycle detection on a sequence generated by a function.