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
Links
https://leetcode.com/problems/find-the-duplicate-number/description/
Video Links
Approach 1:
NlogN using sort
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
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
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
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;
}
};
Similar Problems
Last updated