Find the Duplicate Number

Problem

https://leetcode.com/problems/find-the-duplicate-number/

Given an array of integers nums containing n + 1 integers where each integer is in the range [1, n] inclusive.

There is only one repeated number in nums, return this repeated number.

You must solve the problem without modifying the array nums and using only constant extra space.

Example 1:

Input: nums = [1,3,4,2,2]
Output: 2

Example 2:

Input: nums = [3,1,3,4,2]
Output: 3

Example 3:

Input: nums = [3,3,3,3,3]
Output: 3

Constraints:

• 1 <= n <= 10:sup:`5`

• nums.length == n + 1

• 1 <= nums[i] <= n

• All the integers in nums appear only once except for precisely one integer which appears two or more times.

Follow up:

• How can we prove that at least one duplicate number must exist in nums?

• Can you solve the problem in linear runtime complexity?

Pattern

Array, Two Pointers, Binary Search, Bit Manipulation

Approaches

Negation Marking

Code

def findDuplicate(nums: list[int]) -> int:
    """Find the duplicated number in ``nums``."""
    for i in range(len(nums)):
        n = abs(nums[i])
        if nums[n] < 0:
            return n
        else:
            nums[n] = -nums[n]

    return -1

Test

>>> from find_the_duplicate_number__negation_marking import findDuplicate
>>> findDuplicate([1, 3, 4, 2, 2])
2
>>> findDuplicate([3, 1, 3, 4, 2])
3
>>> findDuplicate([3, 3, 3, 3, 3])
3

find_the_duplicate_number__negation_marking.findDuplicate(nums: list[int]) → int

Find the duplicated number in nums.

Cycle Detection

Explanation

We can view the array as a linked list by starting at i = 0 then setting to i = nums[i]. Because one number is duplicated, two indices will point into the same chain, creating a cycle.

Floyd’s Cycle Detection uses 2 pointers slow and fast which move one step at a time and two steps at a time respectively. If there’s a cycle, they will eventually meet somewhere in the cycle.

To find the duplicate number where the 2 chains meet, we start a new pointer from the beginning, moving both pointers one step at a time. Where they meet again is the duplicate number (the entry point of the cycle).

To see this, let \(L\) be the distance from the start to the cycle entrance, \(C\) the cycle length, and \(k\) the distance from the entrance to where slow and fast first met. Since fast traveled twice as far as slow, the extra distance is a whole number of laps: \(L + k = mC\), so \(L = mC - k\). Walking \(L\) steps from the meeting point is walking back \(k\) steps to the entrance plus \(m\) full laps, landing on the entrance. The new pointer reaches the entrance after exactly \(L\) steps by definition, so the two pointers meet there.

Code

def findDuplicate(nums: list[int]) -> int:
    """Find the duplicate number using Floyd's cycle detection."""
    slow = 0
    fast = 0
    while True:
        slow = nums[slow]
        fast = nums[nums[fast]]
        if slow == fast:
            break

    slow2 = 0
    while slow2 != slow:
        slow = nums[slow]
        slow2 = nums[slow2]

    return slow2

Test

>>> from find_the_duplicate_number__cycle_detection import findDuplicate
>>> findDuplicate([1, 3, 4, 2, 2])
2
>>> findDuplicate([3, 1, 3, 4, 2])
3
>>> findDuplicate([3, 3, 3, 3, 3])
3

Complexity

\(n\) is the number of elements in nums

Measure	Complexity	Notes
Time	\(O(n)\)	slow and fast pointers converge in at most \(L + C\) steps and finding the entrance takes exactly \(L\) steps which are both bounded by \(n\)
Auxiliary Space	\(O(1)\)

find_the_duplicate_number__cycle_detection.findDuplicate(nums: list[int]) → int

Find the duplicate number using Floyd’s cycle detection.