Problem of The Day: Find the Duplicate Number

Problem Statement

My notes:

Need to review different approaches again. They maybe useful for other problems.

Hash set

class Solution:
    def findDuplicate(self, nums: List[int]) -> int:
        hash_set = set()
        for num in nums:
            if num in hash_set:
                return num
            hash_set.add(num)
        return -1

slow and fast approach

class Solution:
    def findDuplicate(self, nums: List[int]) -> int:
        slow = fast = nums[0]
        while True:
            slow = nums[slow]
            fast = nums[nums[fast]]
            if slow == fast:
                break

        slow = nums[0]
        while True:
            if slow == fast:
                return fast
            fast = nums[fast]
            slow = nums[slow]

Editorial Solution

Approach 7: Floyd’s Tortoise and Hare (Cycle Detection)

class Solution:
    def findDuplicate(self, nums):
        # Find the intersection point of the two runners.
        tortoise = hare = nums[0]
        while True:
            tortoise = nums[tortoise]
            hare = nums[nums[hare]]
            if tortoise == hare:
                break

        # Find the "entrance" to the cycle.
        tortoise = nums[0]
        while tortoise != hare:
            tortoise = nums[tortoise]
            hare = nums[hare]

        return hare

Approach 4.2: Array as HashMap (Iterative)

class Solution:
    def findDuplicate(self, nums: List[int]) -> int:
        while nums[0] != nums[nums[0]]:
            nums[nums[0]], nums[0] = nums[0], nums[nums[0]]
        return nums[0]