Find duplicate number in array

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

• Initialize an empty hashmap.
• Iterate over the elements of the array.
• For each element, increase its occurrence count in the hashmap by 1.
• Iterate over the elements of the hashmap.
• For each element in the hashmap, check if its occurrence count is greater than 1. If it is, print the element as a duplicate.
• If no duplicates are found, print a message indicating this.

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;
}

Output

1

TC – O(n)

SC – O(1)