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: 

1
2
3
4
5
6
7
8
Input: [1,3,4,2,2]
Output: 2

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

Input: [2,2,2,2,2]
Output: 2

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.

1
2
3
4
5
6
7
8
public int findDuplicate(int[] nums) {
  Set<Integer> set = new HashSet<>();
  for (int val : nums) {
    if (set.contains(val)) return val;
    set.add(val);
  }
  return -1;
}

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.

1
2
3
4
5
6
7
8
9
public int findDuplicate(int[] nums) {
  Arrays.sort(nums);
  for (int i = 0; i < nums.length; ++i) {
    if (nums[i] == nums[i + 1]) {
      return nums[i];
    }
  }
  return -1;
}

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.

1
2
3
Example: [1, 3, 4, 2, 2]
Index: 0  1  2  3  4
Data:  1  3  4  2  2

The problem can be reduced to as follows:

1
2
3
4
5
6
7
0 --> 1 --> 3 --> 2 --> 4
                  ^     |
                  |-----|

Start with: 0 / 0
1 / 3 --> 3 / 4 --> 2 / 4 --> 4 / 4 --> meet! (1st)
0 / 4 --> 1 / 2 --> 3 / 4 --> 2 / 2 --> meet! (2nd)

We assume that the cycle must exists.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public int findDuplicate(int[] nums) {
  if (nums == null || nums.length == 0) {
    throw new IllegalArgumentException();
  }
  int slow = 0, fast = 0;
  while (true) {
    // move first
    slow = nums[slow];
    fast = nums[nums[fast]]; // all values are in bound
    if (slow == fast) { // they finally meets
      int head = 0;
      while (head != slow) {
        head = nums[head];
        slow = nums[slow];
      }
      break;
    }
  }
  return slow;
}

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