Find duplicate number in array

Written by

studymite

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)