287. Find the Duplicate Number

[#linked-list, #array]

## description

## 287. 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:

plain text

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

Example 2:

plain text

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

Example 3:

plain text

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

Constraints:

–
1 <= n <= 105
–
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.

–
How can we prove that at least one duplicate number must exist in nums?
–
Can you solve the problem in linear runtime complexity?

Follow up:

## notes

### Intuition

Treat the array as a linked list where each value points to the next index. Since there's a duplicate, following these "pointers" creates a cycle. The duplicate is where the cycle begins—finding the cycle's start gives us the answer.

### Implementation

Use Floyd's cycle detection in two phases. First, use fast and slow pointers until they meet—this confirms a cycle and places slow somewhere inside it. Second, start a new pointer at index 0 and advance both it and slow one step at a time. They'll meet at the cycle's start, which is the duplicate value.

### Edge-cases

The first phase only detects that a cycle exists; it doesn't find the start. The second phase is essential for locating the actual duplicate.

–
Time: O(n) — both phases traverse at most n elements
–
Space: O(1) — only using pointers

### Complexity

## solution

python

from typing import List

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

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



if __name__ == "__main__":
    # Include one-off tests here or debugging logic that can be run by running this file
    # e.g. print(solution.two_sum([1, 2, 3, 4], 3))
    solution = Solution()

--EOF--