457. Circular Array Loop
Problem Description
You are playing with a circular array. The array is given in the form of a nums array, and you can move from index i to index j if:
i + nums[i]is cyclic, meaning you can go forward or backward in the array- The direction of movement (forward/backward) must be consistent throughout the cycle
- The cycle should contain at least one element
- The cycle should not contain more than
nelements, wherenis the length ofnums
Return true if there exists a cycle in the array, otherwise return false.
Example 1:
Input: nums = [2,-1,1,2,2]
Output: true
Explanation: There is a cycle from index 0 -> 2 -> 3 -> 0. The cycle's length is 3.Example 2:
Input: nums = [-1,2]
Output: false
Explanation: The sequence from index 1 -> 1 -> 1 ... is not a cycle because the sequence's length is 1.
By definition the sequence's length must be strictly greater than 1 to be a cycle.Example 3:
Input: nums = [-2,1,-1,-2,-2]
Output: false
Explanation: The sequence from index 1 -> 2 -> 1 -> ... is not a cycle because the sequence's movement direction changes.Constraints:
1 <= nums.length <= 5000-1000 <= nums[i] <= 1000nums[i] != 0
Solution
Python Solution
class Solution:
def circularArrayLoop(self, nums: List[int]) -> bool:
n = len(nums)
def get_next(current: int) -> int:
# Calculate next position with modulo to handle circular nature
return (current + nums[current]) % n
# Check each position as a potential start of a cycle
for start in range(n):
if nums[start] == 0:
continue
# Use slow and fast pointers
slow = start
fast = start
# Store the direction of movement
forward = nums[start] > 0
while True:
# Move slow pointer one step
slow = get_next(slow)
if nums[slow] == 0:
break
# Check if direction changes or self-loop
if (nums[slow] > 0) != forward:
break
# Move fast pointer two steps
fast = get_next(fast)
if nums[fast] == 0:
break
if (nums[fast] > 0) != forward:
break
fast = get_next(fast)
if nums[fast] == 0:
break
if (nums[fast] > 0) != forward:
break
# If pointers meet, we found a cycle
if slow == fast:
# Check cycle length > 1
next_pos = get_next(slow)
if next_pos != slow:
return True
break
# Mark visited positions
current = start
while nums[current] != 0 and (nums[current] > 0) == forward:
next_pos = get_next(current)
nums[current] = 0
current = next_pos
return FalseTime Complexity: O(n)
Where n is the length of the input array.
Space Complexity: O(1)
Only constant extra space is used.
Java Solution
class Solution {
public boolean circularArrayLoop(int[] nums) {
int n = nums.length;
for (int start = 0; start < n; start++) {
if (nums[start] == 0) {
continue;
}
// Use slow and fast pointers
int slow = start;
int fast = start;
boolean forward = nums[start] > 0;
while (true) {
// Move slow pointer one step
slow = getNext(nums, slow);
if (nums[slow] == 0) {
break;
}
// Check if direction changes
if ((nums[slow] > 0) != forward) {
break;
}
// Move fast pointer two steps
fast = getNext(nums, fast);
if (nums[fast] == 0) {
break;
}
if ((nums[fast] > 0) != forward) {
break;
}
fast = getNext(nums, fast);
if (nums[fast] == 0) {
break;
}
if ((nums[fast] > 0) != forward) {
break;
}
// If pointers meet, we found a cycle
if (slow == fast) {
// Check cycle length > 1
int next = getNext(nums, slow);
if (next != slow) {
return true;
}
break;
}
}
// Mark visited positions
int current = start;
while (nums[current] != 0 && (nums[current] > 0) == forward) {
int next = getNext(nums, current);
nums[current] = 0;
current = next;
}
}
return false;
}
private int getNext(int[] nums, int current) {
int n = nums.length;
return ((current + nums[current]) % n + n) % n;
}
}Time Complexity: O(n)
Where n is the length of the input array.
Space Complexity: O(1)
Only constant extra space is used.
C++ Solution
class Solution {
public:
bool circularArrayLoop(vector& nums) {
int n = nums.size();
for (int start = 0; start < n; start++) {
if (nums[start] == 0) {
continue;
}
// Use slow and fast pointers
int slow = start;
int fast = start;
bool forward = nums[start] > 0;
while (true) {
// Move slow pointer one step
slow = getNext(nums, slow);
if (nums[slow] == 0) {
break;
}
// Check if direction changes
if ((nums[slow] > 0) != forward) {
break;
}
// Move fast pointer two steps
fast = getNext(nums, fast);
if (nums[fast] == 0) {
break;
}
if ((nums[fast] > 0) != forward) {
break;
}
fast = getNext(nums, fast);
if (nums[fast] == 0) {
break;
}
if ((nums[fast] > 0) != forward) {
break;
}
// If pointers meet, we found a cycle
if (slow == fast) {
// Check cycle length > 1
int next = getNext(nums, slow);
if (next != slow) {
return true;
}
break;
}
}
// Mark visited positions
int current = start;
while (nums[current] != 0 && (nums[current] > 0) == forward) {
int next = getNext(nums, current);
nums[current] = 0;
current = next;
}
}
return false;
}
private:
int getNext(vector& nums, int current) {
int n = nums.size();
return ((current + nums[current]) % n + n) % n;
}
}; Time Complexity: O(n)
Where n is the length of the input array.
Space Complexity: O(1)
Only constant extra space is used.
JavaScript Solution
/**
* @param {number[]} nums
* @return {boolean}
*/
var circularArrayLoop = function(nums) {
const n = nums.length;
const getNext = (current) => {
return ((current + nums[current]) % n + n) % n;
};
for (let start = 0; start < n; start++) {
if (nums[start] === 0) {
continue;
}
// Use slow and fast pointers
let slow = start;
let fast = start;
const forward = nums[start] > 0;
while (true) {
// Move slow pointer one step
slow = getNext(slow);
if (nums[slow] === 0) {
break;
}
// Check if direction changes
if ((nums[slow] > 0) !== forward) {
break;
}
// Move fast pointer two steps
fast = getNext(fast);
if (nums[fast] === 0) {
break;
}
if ((nums[fast] > 0) !== forward) {
break;
}
fast = getNext(fast);
if (nums[fast] === 0) {
break;
}
if ((nums[fast] > 0) !== forward) {
break;
}
// If pointers meet, we found a cycle
if (slow === fast) {
// Check cycle length > 1
const next = getNext(slow);
if (next !== slow) {
return true;
}
break;
}
}
// Mark visited positions
let current = start;
while (nums[current] !== 0 && (nums[current] > 0) === forward) {
const next = getNext(current);
nums[current] = 0;
current = next;
}
}
return false;
};Time Complexity: O(n)
Where n is the length of the input array.
Space Complexity: O(1)
Only constant extra space is used.
C# Solution
public class Solution {
public bool CircularArrayLoop(int[] nums) {
int n = nums.Length;
for (int start = 0; start < n; start++) {
if (nums[start] == 0) {
continue;
}
// Use slow and fast pointers
int slow = start;
int fast = start;
bool forward = nums[start] > 0;
while (true) {
// Move slow pointer one step
slow = GetNext(nums, slow);
if (nums[slow] == 0) {
break;
}
// Check if direction changes
if ((nums[slow] > 0) != forward) {
break;
}
// Move fast pointer two steps
fast = GetNext(nums, fast);
if (nums[fast] == 0) {
break;
}
if ((nums[fast] > 0) != forward) {
break;
}
fast = GetNext(nums, fast);
if (nums[fast] == 0) {
break;
}
if ((nums[fast] > 0) != forward) {
break;
}
// If pointers meet, we found a cycle
if (slow == fast) {
// Check cycle length > 1
int next = GetNext(nums, slow);
if (next != slow) {
return true;
}
break;
}
}
// Mark visited positions
int current = start;
while (nums[current] != 0 && (nums[current] > 0) == forward) {
int next = GetNext(nums, current);
nums[current] = 0;
current = next;
}
}
return false;
}
private int GetNext(int[] nums, int current) {
int n = nums.Length;
return ((current + nums[current]) % n + n) % n;
}
}Time Complexity: O(n)
Where n is the length of the input array.
Space Complexity: O(1)
Only constant extra space is used.
Approach Explanation
The solution uses Floyd's Cycle Finding Algorithm (also known as the "tortoise and hare" algorithm) to detect cycles:
- Key Insights:
- Two-pointer technique
- Direction consistency
- Cycle length check
- Visited marking
- Algorithm Steps:
- Initialize pointers
- Move pointers
- Check conditions
- Mark visited
Implementation Details:
- Circular movement
- Direction tracking
- Cycle detection
- Length verification
Optimization Insights:
- Early termination
- Space optimization
- Visited marking
- Direction check
Edge Cases:
- Single element
- Direction changes
- Self loops
- Multiple cycles