Medium
Fast & Slow Pointers
Find the Duplicate Number
Treat values as next-pointers; the duplicate is a cycle entrance.
Approach
Reading each index's value as a link forms a linked list with a cycle, because a repeated value points two indices to the same place. Use Floyd's cycle detection to find the meeting point, then a second walk from the start to locate the cycle's entry — the duplicate.
Time complexity
O(n)
Space complexity
O(1)
Common mistake
Sorting or using a set — correct but violates the classic O(1) space / no-mutation constraints this problem targets.
See it run, step by step
Generate an interactive lesson for Find the Duplicate Number — trace every variable and watch the algorithm execute until it clicks.
Start a lesson on Find the Duplicate Number