287. Find the Duplicate Number Solution | Leetcode | Binary Search
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 using only constant extra space.
287. Find the Duplicate Number
Difficulty: Medium
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 using 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
Example 3:
Input: nums = [3,3,3,3,3] Output: 3
Constraints:
1 ≤ n ≤ 10⁵nums.length == n + 11 ≤ nums[i] ≤ n- All integers in
numsappear only once except for exactly one integer which appears two or more times.
Follow up:
- How can we prove that at least one duplicate number must exist in
nums? - Can you solve the problem in linear runtime complexity?
Approach:
Since the array contains numbers in the range [1, n] with one duplicate, we can use a binary search on the value range rather than on array indices.
The key observation is that if we pick a number mid between 1 and n and count how many numbers in nums are less than or equal to mid, then:
- If
count <= mid, it means the duplicate is in the upper half (mid + 1ton). - If
count > mid, it means the duplicate lies in the lower half (1tomid).
This property allows us to narrow down the duplicate using a binary search on the possible number range. This approach does not modify the array and uses constant space.
Time Complexity: O(n log n)
Space Complexity: O(1)
class Solution {
public:
int findDuplicate(vector<int>& nums) {
int len = nums.size();
int low = 1;
int high = len-1;
while(low<high){
int mid = (low+high)/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 high;
}
};
Raunit Verma
Technical Writer at CodingKaro
