Skip to content

287. Find the Duplicate Number

Summary

Solution Approach Explanation (1-minute) Time Complexity Space Complexity
Fast-Slow Pointers Treat array as linked list where nums[i] points to index nums[i]. Use Floyd's cycle detection to find where cycle begins (the duplicate). \(O(n)\) \(O(1)\)
Binary Search Binary search on value range [1, n-1]. For each mid value, count numbers <= mid. If count > mid, duplicate is in left half, else right half. \(O(n \log n)\) \(O(1)\)

Implementation

class Solution:
    def findDuplicate(self, nums: List[int]) -> int:
        def getNext(idx: int) -> int:
            return nums[idx]

        slow, fast = 0, 0

        while True:
            slow = getNext(slow)
            fast = getNext(getNext(fast))
            if slow == fast:
                break

        slow2 = 0
        while True:
            slow = getNext(slow)
            slow2 = getNext(slow2)
            if slow == slow2:
                break

        return slow

class Solution:
    def findDuplicate(self, nums: List[int]) -> int:

        low = 1
        high = len(nums) - 1

        while low <= high:
            target = (low + high) // 2

            counts = 0
            for num in nums:
                if num <= target:
                    counts += 1

            if counts <= target:
                low = target + 1
            else:
                duplicate = target
                high = target - 1

        return duplicate