DATA STRUCTURES • ALGORITHMS

Find Duplicate Number

In an array of n+1 integers where each integer is in the range [1, n], finding the single duplicate number using constant extra space.

Time

O(N)

Space

O(1)

Key Principle 1

Floyd's Cycle-Finding Algorithm

Key Principle 2

Tortoise and Hare pointers

Key Principle 3

Array treated as a linked list

Key Principle 4

Guaranteed duplicate existence

FIND_DUPLICATE_LAB
ARRAY (n+1):
Current Step
Floyd's Tortoise and Hare. Treat array as a linked list.
Playback
Cycle Detection ⠿
SLOW (Index)0
FAST (Index)0
Floyd's Logic ⠿
1int slow = arr[0], fast = arr[0];
2do { slow = arr[slow]; fast = arr[arr[fast]]; } while (slow != fast);
3fast = arr[0];
4while (slow != fast) { slow = arr[slow]; fast = arr[fast]; }
5return slow;
1
SLOW
FAST
idx 0
3
idx 1
4
idx 2
2
idx 3
2
idx 4

Loading Lab...