Problems
Cycle in a Circular Array
Hard·Tagsarraytwo-pointers
Problem Statement
We are given an array containing positive and negative numbers. Suppose the array contains a number `M` at a particular index. Now, if `M` is positive we will move forward `M` indices and if `M` is negative move backwards `M` indices.
You should assume that the array is circular which means two things:
1. Moving forward from the last element puts you on the first element.
2. Moving backward from the first element puts you on the last element.
Write a method to determine if the array has a cycle. The cycle should have more than one element and should follow one direction which means the cycle should not contain both forward and backward movements.
Examples
Example 1
Input
arr: [1, 2, -1, 2, 2]Circular array
Output
"true"Why
The array has a cycle among indices: 0 -> 1 -> 3 -> 0. The cycle length is 3 and all movements are forward.
Example 2
Input
arr: [2, 2, -1, 2]Circular array
Output
"true"Why
The array has a cycle among indices: 1 -> 3 -> 1. The cycle length is 2 and all movements are forward.
Example 3
Input
arr: [2, 1, -1, -2]Circular array
Output
"false"Why
The sequence 1 -> 2 -> 1 is a cycle, but it changes direction (forward then backward). Therefore, it is not a valid cycle.
Constraints
- •1 <= arr.length <= 5000
- •-1000 <= arr[i] <= 1000
- •arr[i] != 0
Hints
Stuck? Reveal a nudge toward the right pattern, one step at a time.
Hint 1
Treat the array as a Linked List where the current index represents a node, and the value at that index tells you the number of steps to the next node.
Hint 2
Since the array is circular, you need to use the modulo operator to calculate the next index. For a language like Java or C++, be careful with negative modulo!
Hint 3
Use the Fast and Slow pointers algorithm. For a cycle to be valid, all elements must have the same sign (either all positive or all negative). If a pointer ever changes direction, break out.
Hint 4
A valid cycle must have a length greater than 1. If the fast and slow pointers meet, check if the next step points back to the exact same node.