[LeetCode] 287. Find the Duplicate Number

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.

Note:

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

Thought process:

Based on the conditions, we cannot sort the array or use hashmap. That leaves us with one less obvious solution and one even less obvious solution. 

The first solution is to use binary search on the range of the numbers. Since all numbers are between 1 and n, the duplicate must be either in the range 1 to n / 2, or n / 2 to n. We can count the numbers between 1 and n / 2. If there are n / 2 + 1 numbers, then we can be sure that the duplicate is between 1 and n / 2. Otherwise, it must be in the other half.

Solution:

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 26

class Solution { public: int findDuplicate(vector<int>& nums) { int start = 1; int end = nums.size() - 1; while (start <= end) { int mid = start + (end - start) / 2; int count = 0; for (int num : nums) { if (num <= mid) { count++; } } if (count <= mid) { start = mid + 1; } else { end = mid - 1; } } return start; } };

Time complexity:

While loop takes O(logn). For loop takes O(n). The overall runtime is O(nlogn).

The other solution is less obvious but more efficient. Because all numbers are within range 1 and n, it is safe to use the numbers to index into the array. What would happen if we do this? Suppose the array is [1, 1]. If iterate the array using the elements as index, then we will get an infinite loop at the second 1. Suppose the array is [2, 2, 1]. Then we will get an infinite loop at indexes 1 and 2. The key takeaway is that we will always have a cycle somewhere, and the entrance of the cycle is the duplicate number.

Sounds familiar? Yes, the idea is similar to the classic solution to Linked List Cycle II. We will keep a slow pointer, which goes one step at a time, and a fast pointer, which goes two steps at a time. When they collide, reset the fast pointer to the beginning, and let it go one step of a time. The next time they collide, they will point to the entrance of the cycle, which is our answer.

Solution:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21

class Solution { public: int findDuplicate(vector<int>& nums) { int slow = nums[0]; int fast = nums[nums[0]]; while (slow != fast) { slow = nums[slow]; fast = nums[nums[fast]]; } fast = 0; while (slow != fast) { slow = nums[slow]; fast = nums[fast]; } return slow; } };

Time complexity: O(n).