[LeetCode Road] Find the Duplicate Number - Solution/C++

287. Find the Duplicate Number

Question:

Given an array of integers nums containing n + 1 integers where each integer is in the range [1, n] inclusive.

There is only one repeated number in nums, return this repeated number.

Example:

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

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

Input: nums = [1,1]
Output: 1

Constraints:
2 <= n <= 3 * 10⁴

nums.length == n + 1

1 <= nums[i] <= n

All the integers in nums appear only once except for precisely one integer which appears two or more times.

Source code

Version 1

Idea:
My intuition told me that using unordered_map is a very simple method, however, I knew it's not the question focus.

But, I still offer the unordered_map solution as below.

Time complexity: O(n)
Space complexity: O(n)

class Solution {
public:
    int findDuplicate(vector<int>& nums) {
        const int n = nums.size();
        unordered_map<int, int> record;
        
        for(int i = 0; i < n; i++){
            if(record.count(nums[i])){
                return nums[i];
            }else{
                record[nums[i]] = i;
            }
        }
        return 0;
    }
};

Version 2

Idea:
It's also a very simple method, you sort the all elements before processing. Then, compare nums[i] with nums[i - 1] you will get the answer easily.

Time complexity: O(nlogn)
Space complexity: O(1)

class Solution {
public:
    int findDuplicate(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        
        int res = 0;
        for(int i = 0; i < nums.size() -1; i++){
            int j = i + 1;
            if(nums[i] == nums[j]){
                res = nums[i];
            }
        }
        return res;
    }
};

Version 3

Idea:
The input of vector has duplicate numbers that means those elements can be formed a cycle. And, how to find a duplicate number in a cycle? You can review 141. Linked List Cycle. The answer is Fast & Slow Pointers

At first, delcare two variable as slow and fast. Fast pointer moves 2 steps once and Slow pointer moves 1 steps until these pointers are on the same value.

Then, initial one of pointers to zero, it means starting at the begining.

Finally, two of pointers move 1 step equally and they will stop at the duplicate number.

Time complexity: O(n)
Space complexity: O(1)

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

Version 4

Idea:
As mentioned in question, we know each elements is in the range [1:n] and the vector is containing n + 1. So, we can use Pigeonhole principle.

Using binary search in the range [1:n]. Declare two variable for getting the mid. One is the left index that starts at 1, the other is right index that starts at n - 1.

For each while() processing, use a counter to count how many elements is less than or equal to mid.

If a counter is less than or equal to mid, it's represented a duplicate number on the right side, so move low index to mid + 1.

On the contrary, if a counter is bigger than mid, move high index to mid.

Hence, the search space will be narrowed down.

Time complexity: O(nlogn)
Space complexity: O(1)

class Solution {
public:
    int findDuplicate(vector<int>& nums) {
        const int n = nums.size();
        int low = 1, high = n - 1;
        
        while(low < high){
            int mid = (low + high)/2;
            int count = 0;
            
            for(const int &element:nums){
                if(element <= mid){
                    count++;
                }
            }
            
            if(count <= mid){
                low = mid + 1;
            }else{
                high = mid;
            }
        }
        return low;
    }
};