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] != 0Follow up: Could you solve it in O(n) time complexity and O(1) extra space complexity?
In #457 Circular Array Loop, the goal is to determine whether a circular array contains a valid loop where movement follows a consistent direction (all positive or all negative steps) and the loop length is greater than one. Since the array wraps around, index transitions must be handled using modular arithmetic.
A common and efficient strategy is to use the fast and slow pointer technique (similar to cycle detection in linked lists). For each starting index, move a slow pointer by one step and a fast pointer by two steps using the jump value stored at each index. While traversing, ensure the direction remains consistent; if the sign changes, the current path is invalid. Also ensure that the loop does not consist of a single element pointing to itself.
To avoid redundant work, visited elements can be marked once processed. This approach achieves O(n) time complexity with O(1) extra space by modifying or marking visited indices during traversal.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Two Pointers (Floyd Cycle Detection) | O(n) | O(1) |
| Hash Set / Visited Tracking | O(n) | O(n) |
Sahil & Sarra
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, problems involving cycle detection and array traversal patterns are common in FAANG-style interviews. Circular Array Loop tests knowledge of two-pointer techniques, modular indexing, and edge-case handling.
The optimal approach uses Floyd’s cycle detection algorithm with fast and slow pointers. It checks for cycles while ensuring all steps follow the same direction and the loop length is greater than one.
Direction checks ensure that the loop is either entirely forward or entirely backward. If the traversal changes direction during movement, it violates the problem’s constraints and cannot be considered a valid loop.
The most efficient solution relies on two pointers rather than additional data structures. However, a hash set or visited array can be used to track processed indices if a simpler but less space-efficient solution is preferred.