Two Pointers · Fast & slow on an array LeetCode 287

Find the Duplicate Number / visualized

The constraints do all the work: you may not modify the array and you may use only O(1) extra space. That bans sorting, bans a seen[] set, and bans the negative-marking trick. What is left is a reframing — read the array as a linked list where index i points to nums[i]. Values live in [1, n], so nothing ever points at index 0, which means the walk from 0 must eventually repeat: a cycle. Two indices holding the same value are two nodes with the same successor, so the duplicate is the cycle entrance. From there it is LeetCode 142 verbatim.

Array (n+1 values, each in 1..n)

Execution

idle

Press Run to begin.

0 / 0

Speed

Java · running line

slow — 1 hop fast — 2 hops p — restarted at index 0 entrance = the duplicate unvisited successor edge

O(n) time · O(1) space, and the input is never written to · the answer is the index the two pointers land on, and that index equals the repeated value — because the only way two arrows can converge on one node is for two cells to hold the same number.