Circular Array Loop: Cycles With Direction Constraints

"Circular Array Loop" is a Medium-level staple in Google, Amazon, TikTok loops, and it is a textbook fit for the Fast and Slow Pointers pattern — one of the nine patterns that cover the bulk of what FAANG coding interviews actually test. Part 10 of 11 in the Fast and Slow Pointers arc.

The Problem

In a circular array nums of non-zero integers, each value jumps forward (positive) or backward (negative) that many steps, wrapping around. Return whether a cycle exists that has length greater than 1 and moves in a single direction throughout. The two extra rules — no mixed directions, no self-loops — are what make this the hardest cycle question in the set.

Input:  nums = [2, -1, 1, 2, 2]
Output: True
Indices 0 -> 2 -> 3 -> 0 form a forward-moving cycle.

Recognizing the Fast and Slow Pointers Pattern

Fast and slow pointers (Floyd's tortoise and hare) walk the same structure at different speeds. If there is a cycle they must meet; if there is not, the fast pointer finds the end in half the iterations — which also locates midpoints without knowing the length. It is the default tool for linked lists and for any sequence defined by repeatedly applying a function, all in O(1) space.

Follow-the-index is the same implicit linked list as Find the Duplicate — but the validity constraints mean naive Floyd accepts illegal cycles. The pattern needs guards: abort a walk when direction flips or a step self-loops, and remember dead paths so total work stays linear.

The Approach

From each unvisited start, run slow and fast while every node stepped on shares the start's sign. A meeting means a candidate cycle; reject it if it is a self-loop (next of slow is slow). After abandoning a start, re-walk its path setting values to 0 — a dead-marker no future walk can share a sign with, which is what amortizes the whole thing to O(n).

This zero-marking trick is the difference between O(n) and O(n²), and between a hire and no-hire on this question at Google, where it is reported as a follow-up to simpler cycle problems.

Python Solution

def circular_array_loop(nums: list[int]) -> bool:
    """True if a single-direction cycle of length > 1 exists. Mutates nums."""
    n = len(nums)

    def nxt(i: int) -> int:
        return (i + nums[i]) % n

    for start in range(n):
        if nums[start] == 0:
            continue
        direction = nums[start]
        slow, fast = start, nxt(start)
        while nums[fast] * direction > 0 and nums[nxt(fast)] * direction > 0:
            if slow == fast:
                if slow != nxt(slow):      # reject self-loops
                    return True
                break
            slow = nxt(slow)
            fast = nxt(nxt(fast))
        j = start                           # invalidate the dead path
        while nums[j] * direction > 0:
            k = nxt(j)
            nums[j] = 0
            j = k
    return False

Complexity

• Time: O(n) — zero-marking ensures each index is walked a constant number of times
• Space: O(1) — in-place invalidation instead of a visited set

Interview Tips and Follow-Ups

• If mutation is forbidden, swap zero-marking for a visited array and say the space cost — the interviewer is testing the trade, not the trick.
• Values that are multiples of n create self-loops — index 0 in [3, 1, 2] maps to itself. The slow != nxt(slow) guard rejects it while the genuine 1 -> 2 -> 1 cycle still returns True.
• The sign-product nums[x] * direction > 0 idiom is the clean way to enforce one direction; memorize it.

If this clicked, continue the Fast and Slow Pointers arc in the Technical Interview category. One hundred questions, nine patterns, all in Python.