Home Arrays Write a program to check if there are any duplicated elements in an array? (Method 2)

# Write a program to check if there are any duplicated elements in an array? (Method 2)

0 comment

Question: Given an array of n numbers, give an algorithm for checking whether there are any duplicated elements in the array or not?

Input: 4, 8, 15, 16, 23, 42
Output: NO

Input: 4, 8, 4, 15, 23, 42
Output: YES

Now the question arises, if we can improve the complexity of the above problem. We discussed the most basic method to find duplicates here.
The time complexity can be improved by sorting the given array. After sorting, all the elements with equal values come adjacent to each other. Now, we just need to make one scan of the sorted array and see id there are elements with same value and adjacent. Here is the code for same algorithm:-

int checkDuplicatesSorted(int arr[], int size)
{
quickSort(arr,size);	// sort the array

int duplicate_exist = 0;	//the flag to check duplicates
int i;

for(i=0;i<size-1;i++)
{
//compare the element with its adjacent element
if(arr[i] == arr[i+1])
{
//if we get a duplicate, change the flag and break
duplicate_exist = 1;
break;
}
}

return duplicate_exist;
}


Time Complexity:- O(nlog(n)), for sorting the array.
Space Complexity:- O(1)