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.
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 needs memory for every value, and a sort changes nums. Every value lies between 1 and n, so it is also a valid position: read it as a link. The walk from position 0 ends in a loop whose entrance is the duplicate, and Floyd's two pointers find it in O(n).
Compare every pair
Correct, but does not finish on the largest tests
Intuition
Compare every position with every position after it, and return the value of the first equal pair. Nothing is written and the only memory is two counters, so both rules hold. With 10,001 values and both copies near the end, that is about 5 × 10^7 pair checks.
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. For a cutoff m, count the entries that 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, at most n-m entries are above m, so at least m+1 are at most m. The test "count > m" is false below d and true from d upward, and binary search finds the first m where it turns true.
In the second example, m = 2 counts 2 and 1, not more than 2, and m = 3 still counts 2, so the answer is 4. Each round reads the array once: 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]. With n+1 positions, each with a link, the walk from 0 must revisit a position: a tail, then a loop. The first example goes 0, 2, 1, then round 5, 4.
The loop's entrance is reached from two positions, one on the tail and one on the loop: here positions 1 and 4, which both hold 5. No value is 0, so position 0 is always on the tail and the entrance always has both ways in. Only one value repeats, so the entrance is the answer.
Phase 1 moves slow one link per round and fast two until they meet, after s rounds. The extra s steps of fast were whole laps. Phase 2 restarts slow at 0. After T steps, the tail's length, slow is on the entrance, and fast is where a walk from 0 is after T steps plus whole laps: the entrance too.
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
- Returning the phase 1 meeting point. It is somewhere on the loop: 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. - Starting the walk anywhere but position 0. Position 3 in the first example links to itself, a loop with no way in, so its entrance proves nothing.
- Testing
count >= midin the binary search. When no value from 1 tomrepeats or is missing, the count is exactlym, so only>separates the two sides. - Marking seen values by negating entries or swapping values into place. Both find the answer, but both change the array.
Frequently asked questions3
What is the time complexity of Find the Duplicate Number?
Floyd's cycle detection runs in O(n) time with O(1) extra memory. The binary search on values takes O(n log n) time and O(1) memory, and comparing every pair takes O(n²).
Why not use a hash set or sort the array?
Either works in a real program. The task forbids both: a hash set uses O(n) extra memory, and sorting changes nums or needs a full copy. Those rules 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 array's sum gives the duplicate only when it appears exactly twice. Here a repeat can take the place of missing values: in [4, 2, 4, 1, 4] the difference is 15 minus 10 = 5, a value 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.
def findDuplicate(nums):
# Write code hereTest #1
Test #2
Argument
nums = [2, 5, 1, 3, 5, 4]
Expected Output
5