[Leetcode][287. Find the Duplicate Number] 9 Approaches:Count, Hash, Sorting, Binary Search, Bit Manipulation, Two Pointers

By Long Luo

This article is the solution of Problem 287. Find the Duplicate Number.

Here are 9 approaches to solve this problem in Java.

Inspired by @user2670f and his solution [C++] 7 Different solutions to this problem (with relaxed constraints) added 3 more approaches.

Brute Force (2 Loops)

Since solve the problem without modifying the array nums and uses only constant extra space, we can use Brute Force to solve it.

It’s easy to use 2 loops to do it, but the time complexity is O(n2)O(n^2), so it wouldn’t accepted as timeout.

1
2
3
4
5
6
7
8
9
10
11
12
13
// 2 Loops
public static int findDuplicate_2loops(int[] nums) {
int len = nums.length;
for (int i = 0; i < len; i++) {
for (int j = i + 1; j < len; j++) {
if (nums[i] == nums[j]) {
return nums[i];
}
}
}

return len;
}

Analysis

  • Time Complexity: O(n2)O(n^2)
  • Space Complexity: O(1)O(1)

Count

Count the frequency of the num in the array.

With extra O(n)O(n) space, without modifying the input.

1
2
3
4
5
6
7
8
9
10
11
12
public static int findDuplicate(int[] nums) {
int len = nums.length;
int[] cnt = new int[len + 1];
for (int i = 0; i < len; i++) {
cnt[nums[i]]++;
if (cnt[nums[i]] > 1) {
return nums[i];
}
}

return len;
}

Analysis

  • Time Complexity: O(n)O(n)
  • Space Complexity: O(n)O(n)

Hash

Using a HashSet to record the occurrence of each number.

With extra O(n)O(n) space, without modifying the input.

1
2
3
4
5
6
7
8
9
10
11
public static int findDuplicate_set(int[] nums) {
Set<Integer> set = new HashSet<>();
int len = nums.length;
for (int i = 0; i < len; i++) {
if (!set.add(nums[i])) {
return nums[i];
}
}

return len;
}

Analysis

  • Time Complexity: O(n)O(n)
  • Space Complexity: O(n)O(n)

Marking visited value within the array

Since all values of the array are between [1..n][1..n] and the array size is n+1n+1.

while scanning the array from left to right, we set the nums[n]nums[n] to its negative value.

With extra O(1)O(1) space, with modifying the input.

1
2
3
4
5
6
7
8
9
10
11
12
13
// Visited
public static int findDuplicate_mark(int[] nums) {
int len = nums.length;
for (int num : nums) {
int idx = Math.abs(num);
if (nums[idx] < 0) {
return idx;
}
nums[idx] = -nums[idx];
}

return len;
}

Analysis

  • Time Complexity: O(n)O(n)
  • Space Complexity: O(1)O(1)

Sort

Sorting the array first, then use a loop from 11 to nn.

With extra O(nlogn) space, modifying the input.

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

return len;
}

Analysis

  • Time Complexity: O(nlogn)O(nlogn)
  • Space Complexity: O(logn)O(logn)

Index Sort

If the array is sorted, the value of each array element is its index value index+1index + 1, then we can do this:

  1. If nums[i]==i+1nums[i] == i + 1, it means that the order has been sorted, then skip, i++i++;
  2. If nums[i]==nums[nums[i]1]nums[i] == nums[nums[i] - 1], it means that there is already a value at the correct index, then this value is a duplicated element;
  3. If none of the above is satisfied, exchange the values of nums[i]nums[i] and nums[nums[i]1]nums[nums[i] - 1].

With extra O(logn)O(logn) space, with modifying the input.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// Index Sort
//$n$+ 1 numbers in n.
public static int findDuplicate_index_sort(int[] nums) {
int len = nums.length;
for (int i = 0; i < len; ) {
int n = nums[i];
if (n == i + 1) {
i++;
} else if (n == nums[n - 1]) {
return n;
} else {
nums[i] = nums[n - 1];
nums[n - 1] = n;
}
}

return 0;
}

Analysis

  • Time Complexity: O(n)O(n)
  • Space Complexity: O(1)O(1)

Binary Search

Note that the key is to find an integer in the array [1, 2,…, n] instead of finding an integer in the input array.

We can use the binary search algorithm, each round we guess one number, then scan the input array, narrow the search range, and finally get the answer.

According to the Pigeonhole Principle, n+1n + 1 integers, placed in an array of length nn, at least 11 integer will be repeated.

So guess a number first(the number midmid in the valid range [left,right][left, right]), count the elements of the array which is less than or equal to midmid in the array.

  1. If cntcnt is strictly greater than midmid. According to the Pigeonhole Principle, repeated elements are in the interval [left,mid][left, mid];
  2. Otherwise, the repeated element is in the interval [mid+1,right][mid + 1, right].

With extra O(1)O(1) space, without modifying the input.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public static int findDuplicate_bs(int[] nums) {
int len = nums.length;
int low = 1;
int high = len - 1;
while (low < high) {
int mid = low + (high - low) / 2;
int cnt = 0;
for (int i = 0; i < len; i++) {
if (nums[i] <= mid) {
cnt++;
}
}

if (cnt <= mid) {
low = mid + 1;
} else {
high = mid;
}
}

return low;
}

Analysis

  • Time Complexity: O(nlogn)O(nlogn)
  • Space Complexity: O(1)O(1)

Bit

This method is convert all the numbers to binary numbers. If we can get each digit of the repeated number in binary, we can rebuild the repeated number.

Count all the bits of [1,n][1, n] and array numbers as 11 respectively, and then restore them bit by bit to get this repeated number.

For example, the iith digit, note that in the nums\textit{nums} array, the sum of all the elements whose ith digit is 11 is xx as convert the number to binary.

As the range [1,n][1, n], we can also count the sum of the number whose iith digit is 11, we denoted it yy.

We can easily get that x>yx > y.

The following table lists whether each bit in the binary of each number is 11 or 00 and what the xx and yy of the corresponding bit are:

1 3 4 2 2 x y
Bit 0 1 1 0 0 0 2 2
Bit 1 1 0 1 1 1 3 2
Bit 2 0 0 1 0 0 1 1

From the table, we found that only the 11th bit x>yx > y, so after bitwise restoration target=(010)2=(2)10\textit{target}=(010)_2=(2)_{10}, which is the answer.

The proof of correctness is actually similar to method 11. We can consider the change of the number xx of the ii-th in different example arrays.

  • If target\textit{target} appears twice in the test case array, the rest of the numbers appear once, and the iith bit of target\textit{target} is 11, then the nums\textit{nums} array x, is exactly one greater than y. If bit ii of \textit{target} is 00, then both are equal.

  • If target\textit{target} appears three or more times in the array of test cases, then there must be some numbers that are not in the nums\textit{nums} array. At this time, it is equivalent to replacing these with target\textit{target}, we consider the impact on xx when replacing:

    • If the ii-th bit of the number to be replaced is 11, and the ii-th bit of target\textit{target} is 11: xx remains unchanged, x>yx > y.

    • If the ii-th bit of the number being replaced is 00, and the ii-th bit of target\textit{target} is 11: x plus one, x>yx > y.

    • If the i-th bit of the number to be replaced is 11, and the ii-th bit of target\textit{target} is 00: xx minus one, xyx \le y.

    • If the ii-th bit of the number to be replaced is 00, and the ii-th bit of target\textit{target} is 00: x remains unchanged, satisfying xyx \le y.

Therefore, if the ith bit of target\textit{target} is 11, then after each replacement, only xx will be unchanged or increased. If it is 00, only xx will be unchanged or decreased.

When x>yx > y, the ith bit of target\textit{target} is 11, otherwise it is 00. We only need to restore this repeated number bitwise.

With extra O(nlogn)O(nlogn) space, without modifying the input.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
public static int findDuplicate_bit(int[] nums) {
int n = nums.length;
int ans = 0;
int bit_max = 31;
while (((n - 1) >> bit_max) == 0) {
bit_max -= 1;
}

for (int bit = 0; bit <= bit_max; ++bit) {
int x = 0, y = 0;
for (int i = 0; i < n; ++i) {
if ((nums[i] & (1 << bit)) != 0) {
x += 1;
}
if (i >= 1 && ((i & (1 << bit)) != 0)) {
y += 1;
}
}
if (x > y) {
ans |= 1 << bit;
}
}

return ans;
}

Analysis

  • Time Complexity: O(nlogn)O(nlogn)
  • Space Complexity: O(1)O(1)

Fast Slow Pointers

This problem is as same as 142. Linked List Cycle II, you can refer to this solution for the explanation of the slow fast pointer approach to solve this problem.

The key is to understand how to treat the input array as a linked list.

Take the array [1,3,4,2][1,3,4,2] as an example, the index of this array is [0,1,2,3][0, 1, 2, 3], we can map the index to the nums[n]nums[n].

1
2
3
4
0->1
1->3
2->4
3->2

Start from nums[n]nums[n] as a new index, and so on, until the index exceeds the bounds. This produces a sequence similar to a linked list.

1
0->1->3->2->4->null

If there are a repeated numbers in the array, take the array [1,3,4,2,2][1,3,4,2,2] as an example,

1
2
3
4
5
0->1
1->3
2->4
3->2
4->2

Similarly, a linked list is like that:

1
0->1->3->2->4->2->4->2->…

Here 2>42->4 is a cycle, then this linked list can be abstracted as the following figure:

Link List

With extra O(n)O(n) space, without modifying the input.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public int findDuplicate_fastSlow(int[] nums) {
int slow = 0;
int fast = 0;
do {
slow = nums[slow];
fast = nums[nums[fast]];
} while (slow != fast);

slow = 0;
while (slow != fast) {
slow = nums[slow];
fast = nums[fast];
}

return slow;
}

Analysis

  • Time Complexity: O(n)O(n)
  • Space Complexity: O(1)O(1)

All suggestions are welcome.
If you have any query or suggestion please comment below.
Please upvote👍 if you like💗 it. Thank you:-)

Explore More Leetcode Solutions. 😉😃💗