Reference: LeetCode
Difficulty: Medium

## Problem

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:

Note:

• You must not modify the array (assume the array is read only).
• You must use only constant, $O(1)$ extra space.
• Your runtime complexity should be less than $O(n^2)$.
• There is only one duplicate number in the array, but it could be repeated more than once.

## Analysis

### Hash Set

Note: It uses extra space.

Time: $O(N)$
Space: $O(N)$

### Sorting

If the numbers are sorted, then any duplicate numbers will be adjacent in the sorted array.

Note: It modifies the original array.

Time: $O(N\log{N})$
Space: $O(1)$

### Reduce to Cycle Detection

Reference: Solution Section

We can interpret nums such that for each pair of index i and value val. Then the problem can be reduced to cycle detection. The entry point is the corresponding duplicate number.

The problem can be reduced to as follows:

We assume that the cycle must exists.

Time: $O(N)$
Space: $O(1)$

Comment
Junhao Wang
Hi, I was a master student at USC studying Computer Science.