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)$


Comment