457. Circular Array Loop Solution

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

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:

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:

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?

Approach overview

Problem Overview: You get an integer array where each value represents how many steps to move forward or backward in a circular array. The goal is to determine whether a cycle exists that follows a single direction (all positive or all negative) and contains more than one element.

The tricky part is handling circular movement while ensuring the loop is valid. A loop cannot change direction mid-way and single-element self loops like i -> i are invalid. Efficient solutions rely on cycle detection or marking nodes as processed so they are never revisited.

Approach 1: Floyd's Cycle Detection (Tortoise and Hare) Algorithm (O(n) time, O(1) space)

This approach adapts the classic cycle detection technique used in linked lists. Treat each index as a node and compute the next index using modular arithmetic: next = (i + nums[i]) % n. Two pointers move at different speeds: the slow pointer advances one step while the fast pointer advances two steps.

Before moving pointers, verify that the direction remains consistent. If nums[current] changes sign compared to the starting direction, the path is invalid and you stop exploring it. When slow and fast pointers meet, a cycle exists. One more check ensures the loop length is greater than one by confirming the next index is not the same as the current index. This approach scans each element at most a constant number of times, giving O(n) time with O(1) extra memory. It works well when the problem hints at cycle detection with constant space.

Approach 2: Visited Nodes Marking for Elimination (O(n) time, O(n) space)

Another practical strategy tracks visited nodes while exploring paths from each starting index. Use a Hash Set or marking array to record nodes seen during the current traversal. While moving through the array, ensure every step keeps the same direction. If a node repeats in the current traversal and the loop length is greater than one, a valid cycle exists.

Once a traversal finishes without forming a valid loop, mark every visited node as processed so future iterations skip them. This pruning step prevents repeated work and ensures the overall runtime stays linear. The approach is easier to reason about than pointer racing but uses additional memory for tracking visits.

Both methods rely on efficient index transitions and directional checks. The movement logic itself uses simple arithmetic and modular wrapping to simulate circular traversal.

Recommended for interviews: Floyd’s cycle detection is the expected solution. It demonstrates strong understanding of two pointers and cycle detection patterns while maintaining O(1) space. The visited-marking method is still valuable because it clearly models traversal using a hash table or visited structure, which can help you reason about correctness before optimizing.

Approach 1: Floyd's Cycle Detection (Tortoise and Hare) Algorithm

This approach uses the Tortoise and Hare algorithm to detect cycles. The algorithm involves two pointers, 'slow' and 'fast', with 'slow' moving one step at a time and 'fast' two steps at a time. If there is a cycle in the array, the pointers will eventually meet. However, since this is a circular array, we must also ensure that all elements in the loop have the same direction (all positive or all negative).

Python

class Solution:
    def circularArrayLoop(self, nums):
        n = len(nums)

        def advance(idx):
            return (idx + nums[idx]) % n

        for i in range(n):
            if nums[i] == 0:
                continue
            slow, fast = i, i
            is_forward = nums[i] > 0

            while True:
                slow = advance(slow)
                if nums[slow] == 0 or (nums[slow] > 0) != is_forward:
                    break

                fast = advance(fast)
                if nums[fast] == 0 or (nums[fast] > 0) != is_forward:
                    break
                fast = advance(fast)
                if nums[fast] == 0 or (nums[fast] > 0) != is_forward:
                    break

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

            idx = i
            while nums[idx] != 0 and (nums[idx] > 0) == is_forward:
                next_idx = advance(idx)
                nums[idx] = 0
                idx = next_idx

        return False

Java

class Solution {
    public boolean circularArrayLoop(int[] nums) {
        int n = nums.length;
        for (int i = 0; i < n; i++) {
            if (nums[i] == 0) continue;
            int slow = i, fast = i;
            boolean isForward = nums[i] > 0;

            while (true) {
                slow = advance(nums, slow);
                if (nums[slow] == 0 || (nums[slow] > 0) != isForward) break;

                fast = advance(nums, fast);
                if (nums[fast] == 0 || (nums[fast] > 0) != isForward) break;
                fast = advance(nums, fast);
                if (nums[fast] == 0 || (nums[fast] > 0) != isForward) break;

                if (slow == fast) {
                    if (slow == advance(nums, slow)) break;
                    return true;
                }
            }

            int marker = i;
            while (nums[marker] != 0 && (nums[marker] > 0) == isForward) {
                int next = advance(nums, marker);
                nums[marker] = 0;
                marker = next;
            }
        }
        return false;
    }

    private int advance(int[] nums, int idx) {
        int n = nums.length;
        return ((idx + nums[idx]) % n + n) % n;
    }
}

C++

#include <vector>

class Solution {
public:
    int advance(std::vector<int>& nums, int idx) {
        return ((idx + nums[idx]) % nums.size() + nums.size()) % nums.size();
    }

    bool circularArrayLoop(std::vector<int>& nums) {
        int n = nums.size();
        for (int i = 0; i < n; ++i) {
            if (nums[i] == 0) continue;
            int slow = i, fast = i;
            bool isForward = nums[i] > 0;

            while (true) {
                slow = advance(nums, slow);
                if (nums[slow] == 0 || (nums[slow] > 0) != isForward) break;

                fast = advance(nums, fast);
                if (nums[fast] == 0 || (nums[fast] > 0) != isForward) break;
                fast = advance(nums, fast);
                if (nums[fast] == 0 || (nums[fast] > 0) != isForward) break;

                if (slow == fast) {
                    if (slow == advance(nums, slow)) break;
                    return true;
                }
            }

            int mark = i;
            int val = nums[i];
            while (nums[mark] != 0 && (nums[mark] > 0) == isForward) {
                int next = advance(nums, mark);
                nums[mark] = 0;
                mark = next;
            }
        }
        return false;
    }
};

JavaScript

var circularArrayLoop = function(nums) {
    const n = nums.length;

    const advance = idx => ((idx + nums[idx]) % n + n) % n;

    for (let i = 0; i < n; i++) {
        if (nums[i] === 0) continue;
        let slow = i, fast = i;
        const isForward = nums[i] > 0;

        while (true) {
            slow = advance(slow);
            if (nums[slow] === 0 || (nums[slow] > 0) !== isForward) break;

            fast = advance(fast);
            if (nums[fast] === 0 || (nums[fast] > 0) !== isForward) break;
            fast = advance(fast);
            if (nums[fast] === 0 || (nums[fast] > 0) !== isForward) break;

            if (slow === fast) {
                if (slow === advance(slow)) break;
                return true;
            }
        }

        let mark = i;
        while (nums[mark] !== 0 && (nums[mark] > 0) === isForward) {
            const next = advance(mark);
            nums[mark] = 0;
            mark = next;
        }
    }

    return false;
};

#include <stdbool.h>

int advance(int *nums, int len, int idx) {
    return ((idx + nums[idx]) % len + len) % len;  // Ensure the index is positive.
}

bool circularArrayLoop(int* nums, int numsSize) {
    for (int i = 0; i < numsSize; i++) {
        if (nums[i] == 0) continue;  // Element already visited.
        int slow = i, fast = i;
        bool isForward = nums[i] > 0;

        while (true) {
            slow = advance(nums, numsSize, slow);
            if (nums[slow] == 0 || (nums[slow] > 0) != isForward) break;

            fast = advance(nums, numsSize, fast);
            if (nums[fast] == 0 || (nums[fast] > 0) != isForward) break;
            fast = advance(nums, numsSize, fast);
            if (nums[fast] == 0 || (nums[fast] > 0) != isForward) break;

            if (slow == fast) {
                if (slow == advance(nums, numsSize, slow)) break;
                return true;
            }
        }

        // Mark all seen elements as 0 to avoid redundant work.
        int mark = i;
        int val = nums[i];
        while (nums[mark] != 0 && (nums[mark] > 0) == isForward) {
            int next = advance(nums, numsSize, mark);
            nums[mark] = 0;
            mark = next;
        }
    }
    return false;
}

public class Solution {
    public bool CircularArrayLoop(int[] nums) {
        int n = nums.Length;

        int Advance(int idx) {
            return ((idx + nums[idx]) % n + n) % n;
        }

        for (int i = 0; i < n; i++) {
            if (nums[i] == 0) continue;
            int slow = i, fast = i;
            bool isForward = nums[i] > 0;

            while (true) {
                slow = Advance(slow);
                if (nums[slow] == 0 || (nums[slow] > 0) != isForward) break;

                fast = Advance(fast);
                if (nums[fast] == 0 || (nums[fast] > 0) != isForward) break;
                fast = Advance(fast);
                if (nums[fast] == 0 || (nums[fast] > 0) != isForward) break;

                if (slow == fast) {
                    if (slow == Advance(slow)) break;
                    return true;
                }
            }

            int mark = i;
            int val = nums[i];
            while (nums[mark] != 0 && (nums[mark] > 0) == isForward) {
                int next = Advance(mark);
                nums[mark] = 0;
                mark = next;
            }
        }
        return false;
    }
}

In this Python implementation, we employ the Tortoise and Hare strategy to uncover cycles adhering to the direction constraints. The 'advance' function ensures we stay within bounds, accommodating the circular aspect.

Complexity

Time complexity: O(n) as we process each element once. Space complexity: O(1), utilizing the existing array for marking visited nodes.

Try this approach in the editor

Approach 2: Visited Nodes Marking for Elimination

This approach involves marking each visited index to avoid redundant checks. For each index, try to walk through the array and mark elements until a loop is not possible or a cycle is detected. If a full loop is completed without contradiction, return true. If only part of the array does not form a complete and valid cycle, mark those indices to indicate they can't again lead to a solution.

Python

class Solution:
    def circularArrayLoop(self, nums):
        n = len(nums)

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

            cur = i
            is_forward = nums[cur] > 0
            mark_value = i + 1

            while True:
                next_index = ((cur + nums[cur]) % n + n) % n

                if next_index == cur or nums[next_index] == 0 or (nums[next_index] > 0) != is_forward:
                    break
                if nums[next_index] == mark_value:
                    return True

                nums[cur] = mark_value
                cur = next_index

            cur = i
            while nums[cur] == mark_value:
                next_index = ((cur + nums[cur]) % n + n) % n
                nums[cur] = 0
                cur = next_index

        return False

Java

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

        for (int i = 0; i < n; i++) {
            if (nums[i] == 0) continue;

            int cur = i;
            boolean isForward = nums[cur] > 0;
            int markValue = i + 1;

            while (true) {
                int next = ((cur + nums[cur]) % n + n) % n;

                if (next == cur || nums[next] == 0 || (nums[next] > 0) != isForward) {
                    break;
                }
                if (nums[next] == markValue) return true;

                nums[cur] = markValue;
                cur = next;
            }

            cur = i;
            while (nums[cur] == markValue) {
                int temp = ((cur + nums[cur]) % n + n) % n;
                nums[cur] = 0;
                cur = temp;
            }
        }

        return false;
    }
}

C++

#include <vector>

class Solution {
public:
    bool circularArrayLoop(std::vector<int>& nums) {
        int n = nums.size();

        auto nextIndex = [&](int cur) {
            return ((cur + nums[cur]) % n + n) % n;
        };

        for (int i = 0; i < n; ++i) {
            if (nums[i] == 0) continue;
            int cur = i;
            bool isForward = nums[cur] > 0;
            int markValue = i + 1;

            while (true) {
                int next = nextIndex(cur);
                if (nums[next] == 0 || (nums[next] > 0) != isForward || next == cur) {
                    break;
                }
                if (nums[next] == markValue) return true;

                nums[cur] = markValue;
                cur = next;
            }

            cur = i;
            while (nums[cur] == markValue) {
                int temp = nextIndex(cur);
                nums[cur] = 0;
                cur = temp;
            }
        }

        return false;
    }
};

JavaScript

var circularArrayLoop = function(nums) {
    const n = nums.length;

    for (let i = 0; i < n; i++) {
        if (nums[i] === 0) continue;

        let cur = i;
        const isForward = nums[cur] > 0;
        const markValue = i + 1;

        while (true) {
            const nextIndex = ((cur + nums[cur]) % n + n) % n;

            if (nextIndex === cur || nums[nextIndex] === 0 || (nums[nextIndex] > 0) !== isForward) {
                break;
            }
            if (nums[nextIndex] === markValue) return true;

            nums[cur] = markValue;
            cur = nextIndex;
        }

        cur = i;
        while (nums[cur] === markValue) {
            const temp = ((cur + nums[cur]) % n + n) % n;
            nums[cur] = 0;
            cur = temp;
        }
    }

    return false;
};

#include <stdbool.h>

int nextIndex(int *nums, int len, int index) {
    return ((index + nums[index]) % len + len) % len;
}

bool circularArrayLoop(int* nums, int numsSize) {
    for (int i = 0; i < numsSize; i++) {
        if (nums[i] == 0) continue;  

        int cur = i;
        bool isForward = nums[cur] > 0;
        int markValue = i + 1;

        while (true) {
            int next = nextIndex(nums, numsSize, cur);
            if (nums[next] == 0 || (nums[next] > 0) != isForward) break;
            if (next == cur) break;
            if (nums[next] == markValue) return true;

            nums[cur] = markValue;
            cur = next;
        }

        cur = i;
        while (nums[cur] == markValue) {
            int temp = nextIndex(nums, numsSize, cur);
            nums[cur] = 0;  // Marks the node as visited
            cur = temp;
        }
    }
    return false;
}

public class Solution {
    public bool CircularArrayLoop(int[] nums) {
        int n = nums.Length;

        for (int i = 0; i < n; i++) {
            if (nums[i] == 0) continue;

            int cur = i;
            bool isForward = nums[cur] > 0;
            int markValue = i + 1;

            while (true) {
                int nextIndex = ((cur + nums[cur]) % n + n) % n;

                if (nextIndex == cur || nums[nextIndex] == 0 || (nums[nextIndex] > 0) != isForward) {
                    break;
                }
                if (nums[nextIndex] == markValue) return true;

                nums[cur] = markValue;
                cur = nextIndex;
            }

            cur = i;
            while (nums[cur] == markValue) {
                int temp = ((cur + nums[cur]) % n + n) % n;
                nums[cur] = 0;
                cur = temp;
            }
        }

        return false;
    }
}

This Python rendition simplifies debugging via marker value sweeps that control the state across the whole array with conditional logic on directionality for redundant cycle prevention.

Complexity

Time complexity is O(n), corresponding to the scarcity of auxiliary storage and the space complexity is O(1).

Try this approach in the editor

Approach 3: Default Approach

func circularArrayLoop(nums []int) bool {
	for i, num := range nums {
		if num == 0 {
			continue
		}
		slow, fast := i, next(nums, i)
		for nums[slow]*nums[fast] > 0 && nums[slow]*nums[next(nums, fast)] > 0 {
			if slow == fast {
				if slow != next(nums, slow) {
					return true
				}
				break
			}
			slow, fast = next(nums, slow), next(nums, next(nums, fast))
		}
		j := i
		for nums[j]*nums[next(nums, j)] > 0 {
			nums[j] = 0
			j = next(nums, j)
		}
	}
	return false
}

func next(nums []int, i int) int {
	n := len(nums)
	return (i + nums[i]%n + n) % n
}

Try this approach in the editor

Complexity comparison

Approach	Complexity
Floyd's Cycle Detection (Tortoise and Hare) Algorithm	Time complexity: O(n) as we process each element once. Space complexity: O(1), utilizing the existing array for marking visited nodes.
Visited Nodes Marking for Elimination	Time complexity is O(n), corresponding to the scarcity of auxiliary storage and the space complexity is O(1).
Default Approach	–

Complexity analysis

Approach	Time	Space	When to Use
Floyd's Cycle Detection (Tortoise and Hare)	O(n)	O(1)	Best interview solution when constant space is required and the problem resembles cycle detection.
Visited Nodes Marking	O(n)	O(n)	Useful when clarity is preferred over space optimization and you want explicit tracking of visited indices.

Frequently asked questions

Is Circular Array Loop easy or hard?

Circular Array Loop is generally classified as a medium difficulty problem. The implementation itself is short, but handling circular indices, direction consistency, and rejecting single-element cycles makes the logic slightly tricky.

Circular Array Loop Python/Java solution

Python and Java implementations typically follow Floyd’s cycle detection pattern. Both languages compute the next index using modular arithmetic and move slow and fast pointers until a direction break or cycle detection occurs. The logic remains identical across languages with O(n) time and O(1) space.

How to solve Circular Array Loop in O(n)?

Iterate through the array and treat each index as a starting node. Use slow and fast pointers to simulate movement in the circular array while ensuring both pointers follow the same direction (all positive or all negative). If the pointers meet and the loop length is greater than one, a valid cycle exists. Each invalid path is skipped to keep total work linear.

What is the best approach for Circular Array Loop?

Floyd’s Cycle Detection (Tortoise and Hare) algorithm is the most efficient approach. It treats the array like a linked structure and uses two pointers moving at different speeds to detect cycles. The solution runs in O(n) time and O(1) space while enforcing the rule that the cycle must maintain a single direction and contain more than one element.

Is Circular Array Loop asked at Google/Amazon/Meta?

Circular Array Loop appears in interview preparation sets for companies like Google, Amazon, and Meta because it tests cycle detection and pointer techniques. It also checks whether candidates can enforce constraints such as consistent direction and avoiding single-element loops.

What data structure is used in Circular Array Loop?

The core solution relies on array traversal combined with the two-pointer technique. Some implementations also use a hash set or boolean visited array to mark processed nodes and prevent redundant exploration.

What is the time complexity of Circular Array Loop?

The optimal solution runs in O(n) time because each index is processed a constant number of times while detecting or eliminating paths. Floyd’s cycle detection achieves this with O(1) space, while a visited-set approach may use O(n) additional memory.

Circular Array Loop solution and explanation

The problem

Approach overview

Approach 1: Floyd's Cycle Detection (Tortoise and Hare) Algorithm

Approach 2: Visited Nodes Marking for Elimination

Approach 3: Default Approach

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Circular Array Loop solution and explanation

The problem

Approach overview

Approach 1: Floyd's Cycle Detection (Tortoise and Hare) Algorithm

Approach 2: Visited Nodes Marking for Elimination

Approach 3: Default Approach

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems