Find the Duplicate Number

Medium#287cycle

You get an array of n + 1 numbers, each from 1 to n, so at least one number repeats; exactly one value repeats, maybe more than twice. Find it without changing the array and with O(1) extra memory. Our example: [3, 5, 4, 6, 1, 2, 1], n = 6 — the answer is 1.

287 Find the Duplicate NumberWalkthrough · 1×

Example: [3, 5, 4, 6, 1, 2, 1]: index i links to index nums[i]. Below, the indices in the order the links visit them from 0.

031524364152610361524slow
slowfastthe duplicate and its two cells

No cell holds 0, so no link leads into index 0: it is the head of the list. slow = nums[0] = 3

01/24
restart · back · play · step
Speed
1function findDuplicate(nums):
2 slow = nums[0]
3 fast = nums[nums[0]]
4 while slow != fast:
5 slow = nums[slow]
6 fast = nums[nums[fast]]
7 slow = 0
8 while slow != fast:
9 slow = nums[slow]
10 fast = nums[fast]
11 return slow
state
slow
3
fast
–
historyclick a step to go back

← → step · space play/pause

Why it works

  1. Every value is from 1 to n, so every link leads to a real index and none leads to 0: from 0 the links go on forever, through at most n + 1 indices, so they end in a loop.
  2. The loop starts at the index two links lead into: one from the tail and one from the end of the loop. Two cells hold that index, so it is the duplicate.
  3. Finding where a loop starts is Linked List Cycle II: meet inside, send slow back to the start, step both by one. The array is only read, and two indices are all the memory.

Complexity

Time O(n): each loop takes at most about n steps, as in Linked List Cycle II. Memory O(1): two indices, and the array is not changed.

nextNow solve it yourself, no hints.

Solve on LeetCode ↗

The problem and its statement belong to LeetCode. Here are our own retelling, example and solution. Patterns Hero is not affiliated with LeetCode.