LeetCode 457: Circular Array Loop

Problem Restatement

We are given a circular array nums of non-zero integers.

Each value tells us how far to move from the current index:

nums[i] > 0   # move forward
nums[i] < 0   # move backward

Because the array is circular, moving past the last index wraps around to the first index, and moving before the first index wraps around to the last index.

We need to determine whether there is a valid cycle.

A valid cycle must satisfy three rules:

The official statement describes a cycle as a repeated index sequence where all values have one direction and the cycle length k > 1.

Input and Output

Function shape:

def circularArrayLoop(nums: list[int]) -> bool:
    ...

Examples

Example 1:

nums = [2, -1, 1, 2, 2]

Start at index 0.

0 -> 2 -> 3 -> 0

The values are:

nums[0] = 2
nums[2] = 1
nums[3] = 2

All are positive, and the cycle length is 3.

Answer:

True

Example 2:

nums = [-1, -2, -3, -4, -5, 6]

There are movements, but no valid cycle with one direction and length greater than 1.

Answer:

False

Example 3:

nums = [1, -1, 5, 1, 4]

Index 2 has value 5.

Since the array length is 5, moving 5 steps from index 2 returns to index 2.

That is a self-loop:

2 -> 2

A cycle of length 1 is invalid.

Answer:

False

First Thought: Build a Graph

Each index points to exactly one next index.

For example, if:

nums = [2, -1, 1, 2, 2]

then from index 0:

next = (0 + 2) % 5 = 2

So index 0 points to index 2.

This makes the array behave like a directed graph where each node has one outgoing edge.

A direct idea is:

1. Start from each index.
2. Follow jumps.
3. Track visited indices.
4. Check whether we revisit an index.
5. Reject the cycle if it changes direction or has length 1.

This can work, but we can do it more cleanly with fast and slow pointers.

Problem With Naive Traversal

If we start from every index and use a fresh visited set each time, the same paths may be explored many times.

That can lead to:

O(n^2)

behavior in the worst case.

We want each index to be processed only a constant number of times.

The classic tool for detecting a cycle in a linked structure is Floyd’s cycle detection: one slow pointer and one fast pointer.

Key Insight

Each index has exactly one next index, so walking through the array is like walking through a linked list.

We can use:

slow = next(slow)
fast = next(next(fast))

If slow and fast meet, then there is a cycle.

But this problem has two extra rules:

1. All moves in the cycle must have the same sign.
2. A one-element cycle is invalid.

So while moving pointers, we must ensure that every visited value has the same direction as the starting value.

Next Index Formula

For an index i, the next index is:

(i + nums[i]) % n

In Python, % already gives a non-negative result for positive n.

So this works for both positive and negative moves:

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

Example:

nums = [2, -1, 1, 2, 2]
n = 5

From index 1:

(1 + nums[1]) % 5
= (1 - 1) % 5
= 0

From index 0:

(0 + nums[0]) % 5
= (0 + 2) % 5
= 2

Algorithm

For each index i:

1. Skip it if nums[i] == 0.

   We will use 0 to mark indices that have already been fully checked.

2. Set the direction:

direction = nums[i] > 0

3. Start slow and fast pointers:

slow = i
fast = i

4. Move slow by one step and fast by two steps while both moves keep the same direction.

5. If slow == fast, check whether this is a self-loop.

6. If it is not a self-loop, return True.

7. If no valid cycle is found from this start, mark the explored same-direction path as 0.

If every start fails, return False.

Valid Move Check

We need a helper that tells whether an index can still be used in the current path.

def same_direction(index: int, direction: bool) -> bool:
    return nums[index] > 0 == direction

This means:

In implementation, it is clearer to write:

(nums[index] > 0) == direction

with parentheses.

Walkthrough

Use:

nums = [2, -1, 1, 2, 2]

Start at index 0.

Direction is positive.

Initial:

slow = 0
fast = 0

Move once:

slow = next_index(0) = 2
fast = next_index(next_index(0)) = next_index(2) = 3

Now:

slow = 2
fast = 3

Move again:

slow = next_index(2) = 3
fast = next_index(next_index(3))
     = next_index(0)
     = 2

Now:

slow = 3
fast = 2

Move again:

slow = next_index(3) = 0
fast = next_index(next_index(2))
     = next_index(3)
     = 0

Now:

slow = 0
fast = 0

The pointers meet.

Check self-loop:

next_index(0) = 2

Since 2 != 0, the cycle length is greater than 1.

Return:

True

Correctness

For any fixed starting index, following next_index creates a deterministic path, because each index has exactly one next index.

The fast and slow pointer method detects whether this path enters a cycle. If a cycle exists on that path, the faster pointer eventually catches the slower pointer.

During traversal, we only allow indices whose values have the same sign as the starting value. Therefore, any detected meeting point comes from a path with one consistent direction.

When slow == fast, the algorithm checks:

slow != next_index(slow)

This rejects a cycle of length 1.

So if the algorithm returns True, it found a repeated path with consistent direction and length greater than 1, which is exactly a valid cycle.

If a start does not produce a valid cycle, all indices on that same-direction path can be marked as checked. Starting from any of those indices would follow the same already-failed path or enter the same invalid structure. Marking them as 0 does not remove any possible valid cycle.

Since every unmarked index is eventually tried, the algorithm returns False only when no valid cycle exists.

Complexity

Let n = len(nums).

The algorithm modifies nums by marking checked indices as 0.

Implementation

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

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

        def same_direction(i: int, direction: bool) -> bool:
            return nums[i] != 0 and (nums[i] > 0) == direction

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

            direction = nums[i] > 0
            slow = i
            fast = i

            while True:
                next_slow = next_index(slow)
                next_fast = next_index(fast)

                if not same_direction(next_slow, direction):
                    break

                if not same_direction(next_fast, direction):
                    break

                next_fast_fast = next_index(next_fast)

                if not same_direction(next_fast_fast, direction):
                    break

                slow = next_slow
                fast = next_fast_fast

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

            marker = i
            while same_direction(marker, direction):
                nxt = next_index(marker)
                nums[marker] = 0
                marker = nxt

        return False

Code Explanation

We define:

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

This handles circular movement.

Then:

def same_direction(i: int, direction: bool) -> bool:
    return nums[i] != 0 and (nums[i] > 0) == direction

This checks two things:

1. The index has not already been marked as checked.
2. The move direction matches the current path.

For every possible start:

for i in range(n):

we skip checked indices:

if nums[i] == 0:
    continue

Then we run fast and slow pointers.

The slow pointer moves one step:

next_slow = next_index(slow)

The fast pointer moves two steps, but we validate both steps:

next_fast = next_index(fast)
next_fast_fast = next_index(next_fast)

If either pointer would move into a different direction, the current path cannot form a valid cycle.

When the pointers meet:

if slow == fast:

we reject self-loops:

if slow == next_index(slow):
    break

Otherwise, the cycle is valid:

return True

After a failed start, we mark the explored path with 0:

while same_direction(marker, direction):
    nxt = next_index(marker)
    nums[marker] = 0
    marker = nxt

This prevents repeated work.

Testing

def run_tests():
    s = Solution()

    assert s.circularArrayLoop([2, -1, 1, 2, 2]) is True
    assert s.circularArrayLoop([-1, -2, -3, -4, -5, 6]) is False
    assert s.circularArrayLoop([1, -1, 5, 1, 4]) is False
    assert s.circularArrayLoop([3, 1, 2]) is True
    assert s.circularArrayLoop([-2, -3, -9]) is False
    assert s.circularArrayLoop([1, 1, 1, 1]) is True
    assert s.circularArrayLoop([2, 2, -1, 2]) is True

    print("all tests passed")

run_tests()

Test meaning: