# 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:

```python
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:

| Rule | Meaning |
|---|---|
| Repeats | Following the jumps eventually returns to an earlier index in the cycle |
| Same direction | All values in the cycle are either positive or negative |
| Length greater than 1 | A self-loop does not count |

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

| Item | Meaning |
|---|---|
| Input | A circular array `nums` of non-zero integers |
| Output | `True` if a valid cycle exists, otherwise `False` |
| Forward move | Positive number |
| Backward move | Negative number |
| Invalid cycle | Length `1` or mixed directions |

Function shape:

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

## Examples

Example 1:

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

Start at index `0`.

```python
0 -> 2 -> 3 -> 0
```

The values are:

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

All are positive, and the cycle length is `3`.

Answer:

```python
True
```

Example 2:

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

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

Answer:

```python
False
```

Example 3:

```python
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:

```python
2 -> 2
```

A cycle of length `1` is invalid.

Answer:

```python
False
```

## First Thought: Build a Graph

Each index points to exactly one next index.

For example, if:

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

then from index `0`:

```python
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:

```python
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:

```python
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:

```python
(i + nums[i]) % n
```

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

So this works for both positive and negative moves:

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

Example:

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

From index `1`:

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

From index `0`:

```python
(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:

```python
direction = nums[i] > 0
```

3. Start slow and fast pointers:

```python
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.

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

This means:

| `direction` | Valid values |
|---|---|
| `True` | Positive values |
| `False` | Negative values |

In implementation, it is clearer to write:

```python
(nums[index] > 0) == direction
```

with parentheses.

## Walkthrough

Use:

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

Start at index `0`.

Direction is positive.

Initial:

```python
slow = 0
fast = 0
```

Move once:

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

Now:

```python
slow = 2
fast = 3
```

Move again:

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

Now:

```python
slow = 3
fast = 2
```

Move again:

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

Now:

```python
slow = 0
fast = 0
```

The pointers meet.

Check self-loop:

```python
next_index(0) = 2
```

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

Return:

```python
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:

```python
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)`.

| Metric | Value | Why |
|---|---:|---|
| Time | `O(n)` | Each index is explored and marked at most once |
| Space | `O(1)` | Only pointers and helper variables are used |

The algorithm modifies `nums` by marking checked indices as `0`.

## Implementation

```python
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:

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

This handles circular movement.

Then:

```python
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:

```python
for i in range(n):
```

we skip checked indices:

```python
if nums[i] == 0:
    continue
```

Then we run fast and slow pointers.

The slow pointer moves one step:

```python
next_slow = next_index(slow)
```

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

```python
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:

```python
if slow == fast:
```

we reject self-loops:

```python
if slow == next_index(slow):
    break
```

Otherwise, the cycle is valid:

```python
return True
```

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

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

This prevents repeated work.

## Testing

```python
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:

| Test | Why |
|---|---|
| `[2,-1,1,2,2]` | Standard valid forward cycle |
| `[-1,-2,-3,-4,-5,6]` | No valid cycle |
| `[1,-1,5,1,4]` | Self-loop must be rejected |
| `[3,1,2]` | Valid positive cycle with wraparound |
| `[-2,-3,-9]` | Negative moves with invalid self-loop behavior |
| `[1,1,1,1]` | Whole array forms a valid cycle |
| `[2,2,-1,2]` | Valid cycle among positive indices |