Find the Duplicate Number
You get an array nums of n+1 integers, each between 1 and n. Exactly one value appears more than once, possibly many times, and you return that value.
Solve it without changing nums and with only a constant amount of extra memory.
Function
- numsinteger-array
- n+1 integers, each between 1 and n
- Returnsinteger
- the value that appears more than once
Constraints
1 ≤ n ≤ 104nums.length == n+11 ≤ nums[i] ≤ n- Exactly one value appears two or more times; every other value appears at most once.
Examples
- Input
- nums = [2, 5, 1, 3, 5, 4]
- Output
- 5
- Explanation
- Here
nis 5, and 5 sits at positions 1 and 4, so the answer is 5. Every other value from 1 to 5 appears once.
- Input
- nums = [4, 2, 4, 1, 4]
- Output
- 4
- Explanation
- 4 appears three times, at positions 0, 2 and 4, while 3 does not appear at all. A repeat can take the place of several missing values, so the answer is 4.
+17 hidden tests on Submit
Follow-up
The binary search on values keeps both rules in O(n log n) time. Can you keep them in O(n) time?
Hints
Open them one at a time. Each one gives away a little more.
Every value lies between 1 and
n, and the array has positions 0 ton. So every value is also a valid position. Start at position 0, jump to positionnums[0], then to the position that value names, and so on. What must happen to that walk?The walk never stops and has only
n+1positions to visit, so it falls into a loop. The position where it enters the loop is reached from two different positions, and both of them hold that position as their value.Find the loop's entrance with two pointers from position 0: one jumps once per round, the other twice, until they land on the same position. Then send one back to 0 and move both one jump at a time. They meet at the entrance, which is the answer.
Solution
A hash set or a sort finds the repeat at once, but both break the rules: the set needs memory for every value, and sorting changes nums. The way out is in the numbers. Every value is between 1 and n, so it is also a valid position in the array. Read each value as a link to another position, and following the links from position 0 always ends in a loop whose entrance is the duplicate. Floyd's fast and slow pointers find that entrance with two integers.
Compare every pair
Correct, but does not finish on the largest tests
Intuition
The repeated value sits at two positions i < j at least. Compare every position with every position after it; the first pair that holds equal values gives the answer. In the first example, position 1 holds 5, and the scan from position 2 onward finds another 5 at position 4.
This keeps both rules: nothing is written and the only memory is two loop counters. It is slow because it compares pairs. With n+1 = 10,001 values and both copies near the end, it checks about 5 × 10^7 pairs.
Algorithm
- For each position
ifrom 0 to the end: - For each position
jafteri, comparenums[i]withnums[j]. - Return
nums[i]at the first match.
def findDuplicate(nums):
n = len(nums)
for i in range(n):
for j in range(i + 1, n):
if nums[i] == nums[j]:
return nums[i]
return -1 # unreachable: the input always holds a repeatBinary search on the value
Intuition
Search the range of values, not the positions. Pick a cutoff m and count how many entries of nums are at most m.
If the duplicate d is above m, the values 1 to m each appear at most once, so the count is at most m. If d is at most m, every value above m appears at most once, so at most n-m entries are above m and at least m+1 are at most m. So the test "count > m" is false for every m below d and true from d upward. Binary search finds the first m where it turns true, and that is d.
In the second example, n is 4. For m = 2 the entries 2 and 1 give a count of 2, not more than 2, so the answer is above 2. For m = 3 the count is still 2, so the answer is 4. Each round reads the whole array once and halves the range, so the work is O(n log n): about 14 passes over 10,001 values.
Algorithm
- Set
low= 1 andhigh=n, the length ofnumsminus one. - While
low < high, takemidhalfway between them. - Count the entries of
numsthat are at mostmid. - If the count is greater than
mid, sethigh=mid; otherwise setlow=mid+1. - Return
low.
def findDuplicate(nums):
low, high = 1, len(nums) - 1
while low < high:
mid = (low + high) // 2
# How many values fall in 1..mid?
count = 0
for x in nums:
if x <= mid:
count += 1
if count > mid:
high = mid # 1..mid holds more values than it has room for
else:
low = mid + 1 # the repeat is above mid
return lowFloyd's cycle detection on the value links
Intuition
Read the array as links: position i points to position nums[i]. Every position from 0 to n has exactly one outgoing link, and every link lands somewhere in 1 to n. In the first example the links are 0 → 2, 1 → 5, 2 → 1, 3 → 3, 4 → 5 and 5 → 4.
Start at position 0 and follow the links. The walk can never stop, because every position has a link, and there are only n+1 positions, so it must come back to one it has seen. From then on it goes round forever. The path is a tail followed by a loop, shaped like the letter ρ. In the first example the walk is 0, 2, 1, 5, 4, 5, 4, and so on: the tail is 0, 2, 1 and the loop is 5, 4. Position 3 links to itself, but the walk never reaches it, and that does no harm.
The loop's entrance is the duplicate. The walk enters 5 twice from different places: once from the end of the tail (position 1, because nums[1] is 5) and once from the end of the loop (position 4, because nums[4] is 5). Two different positions hold the value 5, so 5 repeats. The tail always contains position 0, because no value is 0 and nothing ever links back to it, so the entrance always has these two different ways in. Exactly one value repeats, so the entrance is that value.
Now find the entrance with two pointers, as in linked list cycle detection. In phase 1, slow follows one link per round and fast follows two, until they stand on the same position somewhere in the loop. In the first example they meet at 4. In phase 2, put slow back at 0, leave fast where it is, and move both one link per round. They meet at the entrance.
Why phase 2 works: say the tail takes T links to reach the entrance and the loop has C positions. When the pointers met, slow had taken s steps and fast 2s. Both stood on the same spot, so the extra s steps of fast were whole laps of the loop. After T more steps, slow reaches the entrance from 0, and fast stands where a walk from 0 stands after s+T steps, since its extra laps change nothing. That is T steps to the entrance plus s steps, a whole number of laps, which puts it on the entrance too. They cannot meet earlier, because slow is still on the tail and fast never leaves the loop. In the first example slow goes 2, 1, 5 while fast goes 5, 4, 5, and they meet at 5 after T = 3 steps.
Each phase takes O(n) steps, the only memory is two positions, and nums is never written.
Algorithm
- Treat each position
ias a node that links to positionnums[i], and start both pointers at position 0. - Phase 1: move
slowtonums[slow]andfasttonums[nums[fast]]until they are equal. - Phase 2: set
slowback to 0. - Move both one link at a time,
slowtonums[slow]andfasttonums[fast], until they are equal. - Return that position: it is the repeated value.
def findDuplicate(nums):
# Treat each index i as a node with one link, to nums[i].
# Phase 1: slow moves one link, fast moves two, until they meet in the cycle.
slow = fast = 0
while True:
slow = nums[slow]
fast = nums[nums[fast]]
if slow == fast:
break
# Phase 2: restart one pointer at index 0 and move both one link at a time.
# They meet at the cycle's entrance, the index two positions link to.
slow = 0
while slow != fast:
slow = nums[slow]
fast = nums[fast]
return slow
Pitfalls and edge cases
Most wrong answers come from mixing up positions and values, or from stopping Floyd's method one phase early.
- Returning the phase 1 meeting point. It is some position on the loop, not necessarily the entrance. In the first example the pointers meet at 4, but the answer is 5.
- Checking
slow == fastbefore the first move. Both start at 0, so the loop ends at once. Move first, then compare, or start them one and two links ahead. - Starting the walk anywhere but position 0. No link points to position 0, since no value is 0, and that is what guarantees a tail. Starting at another position can put you on a loop with no way in from outside, like position 3 in the first example, whose entrance proves nothing.
- Assuming the duplicate appears exactly twice. The sum trick, total minus
1 + 2 + ... + n, gives 15 minus 10 = 5 on the second example, but the answer is 4. The same goes for XOR tricks. - Binary searching over positions instead of values, or testing
count >= mid. The count of values at mostmis exactlymwhenever no value in 1 tomrepeats and none is missing, so only>separates the two sides. - Marking visited values by negating
nums[x]or swapping values into place. Both work, but both change the array, which the task forbids.
Frequently asked questions4
What is the time complexity of Find the Duplicate Number?
Floyd's cycle detection runs in O(n) time with O(1) extra memory: each of its two phases follows at most a few multiples of n links. The binary search on values takes O(n log n) time and O(1) memory. Comparing every pair is O(n²).
Why does Floyd's cycle detection find the duplicate number?
If you read each value as a link from its position to the position it names, the walk from position 0 must end in a loop, because it never stops and has only n+1 places to go. The position where it enters the loop is reached from two different positions, one on the tail and one on the loop, so two entries hold that value. Floyd's method finds the entrance of a loop with two pointers, so it finds the repeated value.
Why not use a hash set or sort the array?
Both find the answer in O(n) or O(n log n) time, and in a real program either would be fine. The task forbids them on purpose: a hash set uses O(n) extra memory, and sorting either changes nums or needs a full copy. The restrictions are what push you toward the cycle view.
Why does the sum formula not work for Find the Duplicate Number?
Subtracting 1 + 2 + ... + n from the sum of the array gives the duplicate only when it appears exactly twice and every other value appears once. Here the repeat can appear many times and replace missing values. In [4, 2, 4, 1, 4] the difference is 15 minus 10 = 5, which is not even in the array.
Similar problems
Problems that use the same ideas. Solving two or three of them is what makes a pattern stick.
Python
def findDuplicate(nums):
# Write code hereCase 1
Case 2
Input
nums = [2, 5, 1, 3, 5, 4]
Expected
5