#457
Circular Array Loop
expert · 1110 · lc medium +32 · verified · 37% accepted · 825 likes · top 15%
Description
A circular array nums of non-zero integers defines jumps: from index i, move |nums[i]| steps forward when nums[i] > 0 or backward when nums[i] < 0. A valid cycle visits more than one distinct index, loops back to the start, and all steps share the same direction (all positive or all negative).
Return true if such a cycle exists in nums, otherwise false.
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).
Code
1
2
3