Find Duplicate Cycle Entry
MediumPractice library · +20 XPlinked structureshash mapcycle detection
You are given an array next_idx of size N. For each index i from 0 to N-1, next_idx[i] represents the index of the next element in a sequence starting from index 0. This sequence may contain a cycle. Find the index where the cycle begins. If there is no cycle, output -1.
Input
The first line contains an integer N. The second line contains N integers, representing the next_idx array.
Output
Print a single integer: the index where the cycle begins, or -1 if no cycle exists.
Constraints
1 <= N <= 200000 0 <= next_idx[i] < N
Time limit 1 s (native code; slower languages get more)Memory 256 MB14 hidden tests
Example 1
Input
5 1 2 3 4 2
Output
2
Sequence: 0 -> 1 -> 2 -> 3 -> 4 -> 2. Cycle starts at index 2.
Example 2
Input
3 1 2 0
Output
0
Sequence: 0 -> 1 -> 2 -> 0. Cycle starts at index 0.
Hints
Similar problems
- Linked List Path SumMedium
- Cycle Detection and RendezvousMedium
- Find First Duplicate Entry PointMedium
- Array Linked List SimulationMedium
- Find Duplicate Jump TargetMedium
- Linked List Jump GameMedium
More topics: Hash Map and Hashing problems, Linked List problems, Graphs, BFS and DFS problems
# Read the input from stdin and print the answer.
import sys
def main():
data = sys.stdin.read().split()
# your code here
main()
Example 1 input
5 1 2 3 4 2
Example 2 input
3 1 2 0