[Leetcode]287. Find the Duplicate Number

Given an array nums containing n + 1 integers where each integer is between 1 and n (inclusive), prove that at least one duplicate number must exist. Assume that there is only one duplicate number, find the duplicate one.
Example 1:
Input: [1,3,4,2,2] Output: 2
Note:
1. You must not modify the array (assume the array is read only).
2. You must use only constant, O(1) extra space.
3. Your runtime complexity should be less than O(n2).
4. There is only one duplicate number in the array, but it could be repeated more than once.

Binary search – O(nlogn)

To prove that at least one duplicate number must exist, we can apply the Pigeonhole principle. Moreover, we can use the principle to find the duplicate. If we focus on [1..n] as our searching space, we can apply binary-search so that in each iteration, we can narrow down by half of the space.

Setting low=1 and high=n, we have mid=(low+high)//2. Then we will find count – the number of elements in the nums which are less or equal to mid.

  • if count > mid, according to the Pigeonhole principle, the duplicate must exist in [1...mid];
  • if count <= mid, then there are n+1-count elements in [mid+1...n], which means there are at least n+1-mid elements in a range of n-mid. Therefore the duplicate must exist in [mid+1...n].
class Solution:
    def findDuplicate(self, nums: List[int]) -> int:
        n = len(nums)
        low = 1
        high = n - 1
        while low < high:
            mid = (low+high)//2
            if sum(e <= mid for e in nums) <= mid:
                low = mid+1
            else:
                print(nums)
                high = mid
        return low

Floyd’s cycle detection – O(n)

@echoxiaolee provides a brilliant O(n) approach – if we treat this input as a linked list as shown blow, then there are at least two nodes linked to the same node – it becomes a cycle starting point detection problem and we can apply Floyd’s Cycle Detection Algorithm!

Details about the cycle detection are available at Floyd’s Cycle Detection Algorithm so I’d put the code directly:

class Solution:
    def findDuplicate(self, nums: List[int]) -> int:
        slow = nums[0]
        fast = nums[nums[0]]
        while slow != fast:
            slow = nums[slow]
            fast = nums[nums[fast]]
        fast = 0
        while slow != fast:
            slow = nums[slow]
            fast = nums[fast]
        return slow 
Subscribe
Notify of
guest
0 Comments
Inline Feedbacks
View all comments