# Circular Array Loop
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/circular-array-loop)
Canonical: https://scaleengineer.com/dsa/problems/circular-array-loop
**Patterns:** [Two Pointers](https://scaleengineer.com/dsa/patterns/two-pointers)
**Data structures:** Array, Hash Table
---
## Problem
You are playing a game involving a **circular** array of non-zero integers `nums`. Each `nums[i]` denotes the number of indices forward/backward you must move if you are located at index `i`:

* If `nums[i]` is positive, move `nums[i]` steps **forward**, and
* If `nums[i]` is negative, move `nums[i]` steps **backward**.

Since the array is **circular**, you may assume that moving forward from the last element puts you on the first element, and moving backwards from the first element puts you on the last element.

A **cycle** in the array consists of a sequence of indices `seq` of length `k` where:

* Following the movement rules above results in the repeating index sequence `seq[0] -> seq[1] -> ... -> seq[k - 1] -> seq[0] -> ...`
* Every `nums[seq[j]]` is either **all positive** or **all negative**.
* `k > 1`

Return `true` _if there is a **cycle** in_ `nums`_, or_ `false` _otherwise_.

**Example 1:**

![](https://assets.glich.co/dsa/circular-array-loop/image0.jpg) 

**Input:** nums = [2,-1,1,2,2]
**Output:** true
**Explanation:** The graph shows how the indices are connected. White nodes are jumping forward, while red is jumping backward.
We can see the cycle 0 --> 2 --> 3 --> 0 --> ..., and all of its nodes are white (jumping in the same direction).

**Example 2:**

![](https://assets.glich.co/dsa/circular-array-loop/image1.jpg) 

**Input:** nums = [-1,-2,-3,-4,-5,6]
**Output:** false
**Explanation:** The graph shows how the indices are connected. White nodes are jumping forward, while red is jumping backward.
The only cycle is of size 1, so we return false.

**Example 3:**

![](https://assets.glich.co/dsa/circular-array-loop/image2.jpg) 

**Input:** nums = [1,-1,5,1,4]
**Output:** true
**Explanation:** The graph shows how the indices are connected. White nodes are jumping forward, while red is jumping backward.
We can see the cycle 0 --> 1 --> 0 --> ..., and while it is of size > 1, it has a node jumping forward and a node jumping backward, so **it is not a cycle**.
We can see the cycle 3 --> 4 --> 3 --> ..., and all of its nodes are white (jumping in the same direction).

**Constraints:**

* `1 <= nums.length <= 5000`
* `-1000 <= nums[i] <= 1000`
* `nums[i] != 0`

**Follow up:** Could you solve it in `O(n)` time complexity and `O(1)` extra space complexity?

# Approaches
## Brute-Force Traversal
This approach involves a straightforward simulation. We iterate through every element of the array, treating each as a potential starting point of a cycle. For each starting index, we follow the chain of jumps, keeping track of the indices visited in the current path using a `HashSet`. If we encounter an index that's already in our current path set, we've found a cycle. We also need to validate that the cycle has a length greater than 1 and that all its elements have the same sign (all positive or all negative).
**Time:** O(n^2) - For each of the `n` starting indices, the traversal can, in the worst case, visit up to `n` other distinct indices before finding a cycle or terminating. This results in a quadratic time complexity. · **Space:** O(n) - In the worst-case scenario (a single cycle involving all elements), the `HashSet` used for path tracking can store up to `n` indices.
**Pros:** Simple to understand and implement.; Correctly solves the problem by checking all possibilities.
**Cons:** Highly inefficient due to redundant computations. The same subpaths are traversed multiple times from different starting points.; The time complexity of O(n^2) makes it too slow for large inputs.
### Explanation
The brute-force method systematically checks every possible starting point for a cycle. For each index `i` in the `nums` array, we begin a new path traversal.

We use a `HashSet` to keep track of the nodes visited *within the current traversal*. This is crucial for detecting when a path loops back on itself. We also establish the required direction of movement (forward or backward) based on the value of `nums[i]`.

We then follow the jumps from index to index. At each step, we perform three checks:
1.  **Direction Consistency:** The value at the next index must have the same sign as the starting value. If not, this path cannot form a valid cycle, and we abandon it.
2.  **Self-Loop:** The next index cannot be the same as the current index. This would be a cycle of length 1, which is not allowed.
3.  **Cycle Detection:** If the next index is already in our `HashSet`, it means we have re-visited a node in the current path, forming a cycle of length greater than 1. We can immediately return `true`.

If a path terminates due to a direction change or a self-loop, we move on to the next starting index `i+1`. If we check all possible starting points without finding a valid cycle, we return `false`.

```java
import java.util.HashSet;
import java.util.Set;

class Solution {
    public boolean circularArrayLoop(int[] nums) {
        int n = nums.length;
        for (int i = 0; i < n; i++) {
            Set<Integer> path = new HashSet<>();
            int curr = i;
            boolean isForward = nums[i] > 0;

            while (true) {
                // Check for direction change
                if ((nums[curr] > 0) != isForward) {
                    break;
                }

                // Add current node to path and calculate next
                path.add(curr);
                int next = (curr + nums[curr] % n + n) % n;

                // Check for self-loop
                if (next == curr) {
                    break;
                }

                // Check if we've completed a cycle
                if (path.contains(next)) {
                    return true;
                }
                
                curr = next;
            }
        }
        return false;
    }
}
```
### Algorithm
*   Iterate through each index `i` from `0` to `n-1`, treating it as a potential starting point of a cycle.
*   For each starting index `i`, initialize a new `HashSet` called `path_visited` to track the indices in the current traversal path.
*   Determine the direction of movement (forward for positive `nums[i]`, backward for negative) and store it.
*   Start a traversal from `curr = i`.
*   In a loop, calculate the `next` index using the formula `(curr + nums[curr] % n + n) % n`.
*   Check for invalid cycle conditions:
    *   **Self-loop:** If `next == curr`, the cycle has a length of 1, which is invalid. Break the inner loop.
    *   **Mixed directions:** If the sign of `nums[next]` does not match the initial direction, the cycle is invalid. Break the inner loop.
*   Check if `next` is already in `path_visited`. If it is, a cycle has been found. Since self-loops are already handled, this cycle's length is greater than 1. Return `true`.
*   If no cycle is found yet, add `curr` to `path_visited` and update `curr = next` to continue the traversal.
*   If the outer loop completes without finding any valid cycles, return `false`.

## Optimized Traversal with a Visited Array
This approach improves upon the brute-force method by eliminating redundant computations. We use a global `visited` array to keep track of every index that has been part of any traversal. When considering a new starting index `i`, we first check if it has already been visited. If it has, we know that it belongs to a path that has already been explored and determined not to be part of a valid cycle, so we can skip it. This ensures that each index is processed at most a constant number of times, leading to a linear time complexity.
**Time:** O(n) - Each index is visited a constant number of times. The outer loop runs `n` times, but the inner `while` loop's total operations across all iterations of the outer loop are proportional to `n` because of the `visited` array. · **Space:** O(n) - This approach requires an O(n) boolean array for global visited tracking and, in the worst case, an O(n) `HashSet` for local path tracking.
**Pros:** Efficient O(n) time complexity.; Guarantees that each node is processed only once.
**Cons:** Requires extra space proportional to the input size, which might be a constraint in some environments.
### Explanation
The core idea is to remember which nodes we've already analyzed. We introduce a boolean array, `visited`, of the same size as `nums`.

We loop through each index `i` from `0` to `n-1`. Before starting a traversal from `i`, we check `visited[i]`. If it's `true`, we immediately continue to `i+1`, because `i` has already been part of a path that we've fully explored.

If `visited[i]` is `false`, we proceed with a traversal. We still use a temporary `HashSet`, `pathVisited`, to detect cycles specific to the current path. As we visit each node `curr` in this new path, we mark it in both `visited[curr]` and `pathVisited`. 

If our current path intersects with a previously visited node (i.e., `visited[curr]` is true but `curr` is not in `pathVisited`), it means our current path merges into a path that was already confirmed to not contain a valid cycle. We can therefore terminate the current traversal.

This optimization ensures that every node in the array is visited and processed only once across all traversals, bringing the time complexity down from `O(n^2)` to `O(n)`.

```java
import java.util.HashSet;
import java.util.Set;

class Solution {
    public boolean circularArrayLoop(int[] nums) {
        int n = nums.length;
        boolean[] visited = new boolean[n];

        for (int i = 0; i < n; i++) {
            if (visited[i]) {
                continue;
            }
            
            Set<Integer> pathVisited = new HashSet<>();
            int curr = i;
            boolean isForward = nums[i] > 0;

            while (true) {
                if (pathVisited.contains(curr)) {
                    // Cycle found in the current path
                    return true;
                }
                if (visited[curr]) {
                    // Merged into a path that was already checked and found no valid cycle
                    break;
                }

                visited[curr] = true;
                pathVisited.add(curr);

                int next = (curr + nums[curr] % n + n) % n;

                if (next == curr || (nums[next] > 0) != isForward) {
                    break;
                }
                
                curr = next;
            }
        }
        return false;
    }
}
```
### Algorithm
*   Initialize a global boolean array `visited` of size `n` to all `false`.
*   Iterate through each index `i` from `0` to `n-1`.
*   If `visited[i]` is `true`, it means this index was part of a previously checked path, so we can skip it.
*   If `visited[i]` is `false`, start a new traversal from `i`.
*   For this new traversal, use a temporary `path_visited` `HashSet` to detect cycles within the current path only.
*   As you traverse from a node `curr`, first check if it's in `path_visited`. If so, you've found a valid cycle, return `true`.
*   Then check if it's in the global `visited` array. If so, this path merges into an old, invalid path. Stop this traversal.
*   Mark `visited[curr] = true` and add `curr` to `path_visited`.
*   Calculate the `next` index and check for validity (no self-loops, consistent direction).
*   If the path is invalid, break the inner loop. The nodes visited so far are now marked in the global `visited` array, preventing them from being used as starting points again.
*   If the outer loop finishes, return `false`.

## Fast and Slow Pointers with In-place Marking
This optimal solution uses Floyd's cycle-finding algorithm, commonly known as the 'tortoise and the hare' or fast and slow pointers. It achieves `O(n)` time and `O(1)` space complexity. For each potential starting point, we launch a slow pointer (moves one step) and a fast pointer (moves two steps). If they meet, we've found a cycle. To achieve `O(n)` time overall, we avoid re-processing by marking the nodes of any traversed path as invalid. We can do this in-place by setting the corresponding `nums` value to 0, as the problem statement guarantees all original numbers are non-zero.
**Time:** O(n) - Each element of the array is visited a constant number of times. The marking strategy ensures that each component of the underlying graph is processed only once. · **Space:** O(1) - The algorithm operates in-place on the input array. No auxiliary data structures that scale with the input size are used.
**Pros:** Optimal solution with O(n) time and O(1) space complexity.; Efficiently handles cycle detection using a well-known algorithm.
**Cons:** This approach modifies the input array, which might be undesirable if the original array needs to be preserved.; The logic is more complex to implement correctly compared to the other approaches.
### Explanation
This approach treats the array as a functional graph where each index is a node with exactly one outgoing edge. We are looking for a cycle in this graph that meets the problem's criteria.

We iterate through each index `i`. If `nums[i]` is not 0 (our mark for a visited/invalid path), we start a cycle detection process from `i`.

Two pointers, `slow` and `fast`, are initialized at `i`. In each iteration, `slow` advances one step and `fast` advances two steps. A helper function, `getNext`, calculates the next index while also enforcing the problem's rules:
1.  **Consistent Direction:** The move is only valid if `nums[next_index]` has the same sign as `nums[i]`.
2.  **No Self-Loops:** The move is invalid if `next_index` is the same as `current_index`.
If a move is invalid, `getNext` returns a sentinel value like -1, causing the search along that path to terminate.

If `slow` and `fast` pointers meet at a valid index, we have found a cycle that adheres to all conditions, and we can return `true`.

If the search from `i` terminates without finding a cycle (because a pointer hit an invalid move), we must prevent this path from being re-analyzed. We do this by traversing the path again from `i` and setting each `nums` value to 0. This ensures that each node in the graph is part of a fast/slow pointer search at most once, guaranteeing an overall `O(n)` time complexity with `O(1)` extra space.

```java
class Solution {
    public boolean circularArrayLoop(int[] nums) {
        int n = nums.length;
        if (n <= 1) {
            return false;
        }

        for (int i = 0; i < n; i++) {
            // Skip if element is 0, as it indicates a processed path
            if (nums[i] == 0) {
                continue;
            }

            int slow = i, fast = i;
            boolean isForward = nums[i] > 0;

            do {
                slow = getNext(slow, nums, n, isForward);
                fast = getNext(fast, nums, n, isForward);
                if (fast != -1) {
                    fast = getNext(fast, nums, n, isForward);
                }
            } while (slow != -1 && fast != -1 && slow != fast);

            if (slow != -1 && slow == fast) {
                return true;
            }

            // Mark the path as visited (invalid) by setting elements to 0
            int curr = i;
            boolean currentDirection = nums[curr] > 0;
            while (currentDirection == isForward && nums[curr] != 0) {
                int next = (curr + nums[curr] % n + n) % n;
                nums[curr] = 0;
                curr = next;
            }
        }

        return false;
    }

    private int getNext(int curr, int[] nums, int n, boolean isForward) {
        // A 0 indicates a previously visited invalid path
        if (nums[curr] == 0) {
            return -1;
        }
        // Check for direction consistency
        if ((nums[curr] > 0) != isForward) {
            return -1;
        }
        
        int next = (curr + nums[curr] % n + n) % n;
        
        // Check for self-loop
        if (next == curr) {
            return -1;
        }
        
        return next;
    }
}
```
### Algorithm
*   Iterate through each index `i` from `0` to `n-1`.
*   If `nums[i]` is 0, this index belongs to a path that has already been processed and found to be invalid. Skip it.
*   Initialize two pointers, `slow` and `fast`, both to `i`. Also, determine the required direction `is_forward` from `nums[i]`.
*   Enter a loop to move the pointers:
    *   Advance `slow` by one step using a helper function `getNext`.
    *   Advance `fast` by two steps, calling `getNext` twice.
    *   The `getNext` helper function should check for path validity. It takes the current index, the array, and the required direction. It returns the next index if the move is valid (same direction, not a self-loop), and a special value (e.g., -1) if it's invalid.
    *   If at any point `slow` or `fast` becomes -1, the path is invalid. Break the pointer-moving loop.
    *   If `slow` and `fast` become equal (and are not -1), a valid cycle has been found. Return `true`.
*   If the pointer-moving loop terminates without returning `true`, it means the path starting from `i` is invalid. Mark this entire path by traversing it again from `i` and setting the values `nums[j]` to 0.
*   If the main loop finishes, no valid cycles were found. Return `false`.

# Solutions
### Java

```java
class Solution { private int n ; private int [] nums ; public boolean circularArrayLoop ( int [] nums ) { n = nums . length ; this . nums = nums ; for ( int i = 0 ; i < n ; ++ i ) { if ( nums [ i ] == 0 ) { continue ; } int slow = i , fast = next ( i ); while ( nums [ slow ] * nums [ fast ] > 0 && nums [ slow ] * nums [ next ( fast )] > 0 ) { if ( slow == fast ) { if ( slow != next ( slow )) { return true ; } break ; } slow = next ( slow ); fast = next ( next ( fast )); } int j = i ; while ( nums [ j ] * nums [ next ( j )] > 0 ) { nums [ j ] = 0 ; j = next ( j ); } } return false ; } private int next ( int i ) { return ( i + nums [ i ] % n + n ) % n ; } }
```

### CPP

```cpp
class Solution { public: bool circularArrayLoop ( vector < int >& nums ) { int n = nums . size (); for ( int i = 0 ; i < n ; ++ i ) { if ( ! nums [ i ]) continue ; int slow = i , fast = next ( nums , i ); while ( nums [ slow ] * nums [ fast ] > 0 && nums [ slow ] * nums [ next ( nums , fast )] > 0 ) { if ( slow == fast ) { if ( slow != next ( nums , slow )) return true ; break ; } slow = next ( nums , slow ); fast = next ( nums , next ( nums , fast )); } int j = i ; while ( nums [ j ] * nums [ next ( nums , j )] > 0 ) { nums [ j ] = 0 ; j = next ( nums , j ); } } return false ; } int next ( vector < int >& nums , int i ) { int n = nums . size (); return ( i + nums [ i ] % n + n ) % n ; } };
```

### Python

```python
class Solution : def circularArrayLoop ( self , nums : List [ int ]) -> bool : n = len ( nums ) def next ( i ): return ( i + nums [ i ] % n + n ) % n for i in range ( n ): if nums [ i ] == 0 : continue slow , fast = i , next ( i ) while nums [ slow ] * nums [ fast ] > 0 and nums [ slow ] * nums [ next ( fast )] > 0 : if slow == fast : if slow != next ( slow ): return True break slow , fast = next ( slow ), next ( next ( fast )) j = i while nums [ j ] * nums [ next ( j )] > 0 : nums [ j ] = 0 j = next ( j ) return False
```