Watch 10 video solutions for Circular Array Loop, a medium level problem involving Array, Hash Table, Two Pointers. This walkthrough by Abhishek Jaiswal has 5,400 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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:
nums[i] is positive, move nums[i] steps forward, andnums[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:
seq[0] -> seq[1] -> ... -> seq[k - 1] -> seq[0] -> ...nums[seq[j]] is either all positive or all negative.k > 1Return 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?
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 | 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. |