Circular Array Loop - Solution & Explanation
Problem Statement
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, movenums[i]steps forward, and - If
nums[i]is negative, movenums[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] <= 1000nums[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).
In this solution, we use a function 'advance' to calculate the next index while ensuring it stays within bounds. For each element, we check if it can be the start of a cycle. We use the Tortoise and Hare approach to detect cycles, verifying if all elements are moving in the same direction.
Complexity
Time complexity: O(n) since each element is processed at most twice. Space complexity: O(1) as we use a constant amount of extra space.
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.
This C code marks visited nodes with a special value to limit the state space and eliminate nodes that do not lead to cycles. This allows the logic to identify cycles efficiently without repeating work already done.
Complexity
Time complexity: O(n), since every element is processed at most twice. Space complexity: O(1), as no extra space beyond input is utilized.
Approach 3: Default Approach
Try this approach in the editor →Complexity Comparison
| Approach | Complexity |
|---|---|
| Floyd's Cycle Detection (Tortoise and Hare) Algorithm | Time complexity: O(n) since each element is processed at most twice. Space complexity: O(1) as we use a constant amount of extra space. |
| Visited Nodes Marking for Elimination | Time complexity: O(n), since every element is processed at most twice. Space complexity: O(1), as no extra space beyond input is utilized. |
| Default Approach | — |
Detailed 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. |
Video Solution
Day 11/90 |⚡457. Circular Array Loop | Fast & Slow Pointers Pattern | DSA Pattern • CTO Bhaiya • 6,187 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Circular Array Loop easy or hard?
Circular Array Loop Python/Java solution
How to solve Circular Array Loop in O(n)?
What is the best approach for Circular Array Loop?
Is Circular Array Loop asked at Google/Amazon/Meta?
What data structure is used in Circular Array Loop?
What is the time complexity of Circular Array Loop?
Ready to solve this problem?
Practice Circular Array Loop with our built-in code editor and test cases.
Practice on FleetCodeProblem Info
Table of Contents
Practice this problem
Open in Editor