DSA Tracker

Visualize

Find the Duplicate Number

Floyd's cycle detection, reused from linked lists

time O(n)space O(1)

n+1 numbers squeezed into the range [1,n] guarantees at least one repeat by pigeonhole — but the clever part is turning the ARRAY into a linked list: treat each index i as a node whose 'next' pointer is nums[i]. A repeated value means two different indices point to the same next-index, which is exactly what creates a cycle — and a cycle's entry point is found with the same slow/fast pointer trick used for linked lists.

Details

Animated on: nums = [1,3,4,2,2] — find the one repeated number without modifying the array or using extra space.

Problem:Find the Duplicate NumberMedium

Floyd's cycle detection, reused from linked lists

step 1 / 9

1
[0]
3
[1]
4
[2]
2
[3]
2
[4]

nums=[1,3,4,2,2]. Treat each value as a "next pointer": index i points to index nums[i]. A duplicate value means two indices point to the same place — a cycle. Find it with Floyd's slow/fast pointers.

Pseudocode
1FUNCTION findDuplicate(nums):
2  set slow to nums[0], fast to nums[nums[0]]
3  WHILE slow is not equal to fast:
4    move slow to nums[slow] (one hop), fast to nums[nums[fast]] (two hops)
5  set p1 to 0, p2 to fast
6  WHILE p1 is not equal to p2:
7    move p1 to nums[p1] and p2 to nums[p2] (one hop each)
8  RETURN p1

← / → step · space play · Home restart

Every step in words

Show all 9 steps
  1. nums=[1,3,4,2,2]. Treat each value as a "next pointer": index i points to index nums[i]. A duplicate value means two indices point to the same place — a cycle. Find it with Floyd's slow/fast pointers.
  2. slow = nums[0] = 1, fast = nums[nums[0]] = 3. slow moves one hop per step, fast moves two.
  3. slow -> 3, fast -> 4.
  4. slow -> 2, fast -> 4.
  5. slow -> 4, fast -> 4. They meet — a cycle is confirmed (this doesn't yet reveal WHERE the duplicate is, only that one exists).
  6. Phase 2: reset one pointer to the start (index 0), keep the other at the meeting point. Move BOTH one hop at a time now — they're mathematically guaranteed to meet exactly at the cycle's entrance, which is the duplicate value.
  7. p1 -> 1, p2 -> 2.
  8. p1 -> 3, p2 -> 4.
  9. p1 -> 2, p2 -> 2. They meet at 2 — that's the duplicate.

Now solve it yourself

Watching is the first half. The second is writing it without the animation.

Solve Find the Duplicate Number in the editorAll Arrays problemsBack to roadmap