& Code
Brute Force Approach
Sort the given array and run a loop to find the duplicate number.
TC – O(nlogn) | SC – O(1)
Better Approach
Using HashMap
Keep all the elements of the array in a hashmap with their occurrence count. And after this traverse the map elements, element having occurrence count greater than 1 are duplicates.
TC – O(n)
SC – O(n)
Optimal Approach
Using Floyd Cycle detection
We will take two pointers one will move fast and one slow.
#include<bits/stdc++.h>
using namespace std;
int findDuplicates(int arr[], int arrSize){
int fast = 0,
slow = 0;
do{
slow = arr[slow];
fast = arr[arr[fast]];
} while(slow != fast);
slow = 0;
while(slow != fast){
slow = arr[slow];
fast = arr[fast];
}
return slow; //or fast
}
int main(){
int arrWithDuplicates[] = {2,5,1,1,4,3};
int arrSize = sizeof(arrWithDuplicates)/sizeof(arrWithDuplicates[0]);
cout<<findDuplicates(arrWithDuplicates, arrSize);
return 0;
}TC – O(n)
SC – O(1)
Report Error/ Suggestion