Description
An array of n + 1 values in 1..n contains one distinct repeated number, possibly more than twice. Find it without modifying the array and using constant extra space.
Solution
def find_duplicate(nums):
slow = fast = 0
while True:
slow = nums[slow]
fast = nums[nums[fast]]
if slow == fast:
break
entry = 0
while entry != slow:
entry = nums[entry]
slow = nums[slow]
return entryExamples
Example 1
- Input
[[1,3,4,2,2]]- Output
2
2 appears twice.
Example 2
- Input
[[3,1,3,4,2]]- Output
3
3 repeats.
Example 3
- Input
[[2,2,2]]- Output
2
One distinct value may appear several times.
Approach
Treat values as next indices in a functional graph. Floyd's slow and fast pointers meet in a cycle. Reset one to index zero and advance both one step until they meet at the cycle entry, the duplicate.
Time & space
O(n) time and O(1) auxiliary space, where n + 1 is the array length.