287. Find the Duplicate Number

Problem Statement

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.

You must solve the problem without modifying the array nums and uses only constant extra space.

Example 1:

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

Example 2:

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

Constraints:

1 <= n <= 105
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.

Intuition

https://leetcode.com/problems/find-the-duplicate-number/solutions/1892872/c-6-approaches-interview-question/

Follow this link for explanations

Video Links

Approach 1:

NlogN using sort

C++

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

        return -1;
    }
};

Approach 2:

N Time + N Space using map

C++

class Solution {
public:
    int findDuplicate(vector<int>& nums) {
        unordered_map<int, int> mp;
        for(auto &it: nums){
            if(mp.find(it) == mp.end())
                mp[it]++;
            else
                return it;
        } 

        return -1;
    }
};

Approach 3:

NlogN Time + 1 Space using BS

C++

class Solution {
public:
    int findDuplicate(vector<int>& nums) {
        int low = 1, high = nums.size() - 1, cnt;
        
        while(low <=  high)
        {
            int mid = low + (high - low) / 2;
            cnt = 0;
            // cnt number less than equal to mid
            for(int n : nums)
            {
                if(n <= mid)
                    ++cnt;
            }
            // binary search on left
            if(cnt <= mid)
                low = mid + 1;
            else
            // binary search on right
                high = mid - 1;
            
        }
        return low;
    }
};

Approach 4:

Important method , N Time + 1 Space 

Marking the index 

Basically we treat elements as index and 
LEt say we get 4, we make nums[4] as -nums[4]

But duplicate element will cause double changes, will get caught

C++

class Solution {
public:
    int findDuplicate(vector<int>& nums) {
        int n = nums.size();
        
        for(int i = 0; i < n; ++i){
            int idx = abs(nums[i]);
            
            if(nums[idx] < 0)
                return idx;
            
            nums[idx] = -nums[idx];
        }
        
        return n;
    }
};