Circular Array Loop: Fast and Slow Pointers in a Ring

Circular Array Loop is LeetCode problem 457. You are given a circular array of non-zero integers. Each element tells you how many indices to jump forward (positive) or backward (negative). Your goal is to determine whether there exists a cycle that visits more than one index and always moves in the same direction (all forward or all backward). This is a classic application of Floyd's cycle detection, but with extra constraints that make it trickier than the standard linked list version.

The problem

You are given a circular integer array nums of length n. A cycle in the array consists of a sequence of indices seq of length k where:

• Following the movement rules from each index seq[i] leads to seq[(i + 1) % k]
• Every nums[seq[i]] has the same sign (all positive or all negative)
• k > 1 (the cycle must visit more than one index)

Movement rule: from index i, the next index is (i + nums[i]) % n. If nums[i] is negative, you wrap backward. Since the array is circular, index arithmetic is always modulo n.

Return true if any such cycle exists, false otherwise.

Why this problem matters

Circular Array Loop tests your ability to adapt a well-known algorithm to a new setting. Floyd's cycle detection is standard for linked lists, but applying it to a circular array with direction and length constraints requires careful thought. Interviewers love this problem because it separates candidates who memorize solutions from those who truly understand the underlying pattern.

The key insight

Think of the array as an implicit graph. Each index has exactly one outgoing edge determined by (i + nums[i]) % n. Since every node has exactly one successor, the structure is a collection of "rho" shapes: tails leading into cycles. Any walk from any node will eventually enter a cycle.

The challenge is that not every cycle in this graph is valid. You need two additional checks:

1. Same direction. Every element in the cycle must have the same sign. A cycle that mixes forward and backward jumps does not count.
2. Length greater than 1. A self-loop (an index that points to itself) does not count.

Floyd's algorithm finds cycles efficiently. You run slow and fast pointers starting from each index. If they meet, you check whether the cycle satisfies both constraints. If you detect that the direction changes during traversal, you can bail out early.

The optimization that makes this O(n) overall is marking visited indices. Once you have explored all indices reachable from a starting point and found no valid cycle, you mark them. Future iterations skip these indices, so each index is processed at most twice across all starting points.

The code

def circularArrayLoop(nums: list[int]) -> bool:
    n = len(nums)

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

    for i in range(n):
        if nums[i] == 0:
            continue

        slow, fast = i, i
        while True:
            slow = next_idx(slow)
            fast = next_idx(next_idx(fast))

            if nums[slow] * nums[i] < 0 or nums[fast] * nums[i] < 0 or nums[next_idx(fast)] * nums[i] < 0:
                break

            if slow == fast:
                if slow == next_idx(slow):
                    break
                return True

        j = i
        while nums[j] * nums[i] > 0:
            nxt = next_idx(j)
            nums[j] = 0
            j = nxt

    return False

Why this works

The algorithm tries each index as a potential cycle start. For each starting index i:

1. Initialize slow and fast pointers at index i.
2. Advance pointers. Slow moves one step. Fast moves two steps.
3. Direction check. Before each advance, verify that the current element has the same sign as nums[i]. If the direction changes, this path cannot form a valid cycle. Break out.
4. Cycle detection. If slow and fast meet at the same index, a cycle exists. Check the length constraint: if the next index from the meeting point is itself, the cycle has length 1 (a self-loop). Otherwise, return true.
5. Mark visited. If no valid cycle was found from index i, walk back through the path and set each visited element to 0. This prevents future iterations from re-exploring dead-end paths.

The marking step is what keeps the overall time at O(n). Without it, you could revisit the same indices from different starting points, leading to O(n^2) behavior.

Visual walkthrough

Let's trace through nums = [2, -1, 1, 2, 2]. The algorithm tries each index as a starting point, using slow and fast pointers to search for a valid cycle.

Starting from index 0, the slow and fast pointers converge at the same index. The cycle visits indices 0, 2, and 3, all of which have positive values. The cycle length is 3. Both constraints are satisfied, so the answer is true.

Complexity analysis

Time: O(n). Each element is visited at most twice: once during the pointer traversal and once during the marking phase. Once an element is set to 0, it is never visited again. Across all iterations, the total work is proportional to n.

Space: O(1). The algorithm modifies the input array in place to mark visited elements. No additional data structures are used beyond a few pointer variables. If you cannot modify the input, you can use a separate visited array for O(n) space.

Building blocks

Floyd's cycle detection on implicit graphs

The core technique is the same as detecting cycles in a linked list. Each array index has exactly one successor, so the structure is functionally identical to a singly linked list. The slow pointer moves one hop, the fast pointer moves two, and if a cycle exists, they will meet. The key adaptation here is that you must verify the direction and length constraints after detecting a meeting point.

Direction-constrained traversal

The direction constraint means you cannot just find any cycle. You need every node in the cycle to agree on whether movement is forward or backward. This is checked incrementally during traversal by comparing the sign of each visited element against the sign of the starting element. If a sign mismatch is found, the traversal aborts immediately.

In-place marking for amortized efficiency

Setting visited elements to 0 is a common trick for avoiding repeated work in array problems. It turns a potentially quadratic algorithm into a linear one. The insight is that any element on a path that does not lead to a valid cycle will never lead to one from a different starting point either, because the successor function is fixed.

Edge cases

• Self-loops. If nums[i] % n == 0, the index points to itself. This is not a valid cycle because the length must be greater than 1. The algorithm explicitly checks for this.
• All elements have the same sign. If every value is positive (or every value is negative), you only need to find any cycle of length greater than 1. The direction constraint is automatically satisfied.
• Single element array. With n = 1, any index points to itself. No valid cycle exists because length must exceed 1. Return false.
• Large negative values. The modular arithmetic (i + nums[i]) % n can produce negative results in some languages. In Python, the % operator always returns a non-negative result, but in languages like Java or C++, you need to handle this explicitly: ((i + nums[i]) % n + n) % n.

From understanding to recall

Circular Array Loop combines Floyd's cycle detection with two extra constraints: same direction and length greater than 1. The direction check during traversal and the in-place marking for efficiency are the parts most people forget when they try to reproduce this solution. The algorithm structure itself (try each index, run slow/fast, mark dead ends) is worth typing from memory a few times until it sticks.

The pattern of adapting Floyd's algorithm to new domains, such as arrays treated as implicit linked lists, shows up in multiple LeetCode problems. Once you internalize the mapping from "array values as next pointers" to "implicit graph structure," you will recognize it quickly in problems like Find the Duplicate Number and Happy Number.

Related posts

• Linked List Cycle - Floyd's cycle detection on linked lists, the foundation this problem builds on
• Linked List Cycle II - Finding the cycle entry point, which deepens your understanding of the two-phase technique
• Find the Duplicate Number - Another problem where array values serve as implicit pointers, solved with Floyd's algorithm