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

Related Posts:

• Diameter of a Binary Tree
• Merge two sorted arrays in C++
• Next Larger Element
• Sort an array of 0s, 1s, 2s
• Height of a Binary Tree