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

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)

You can download the complete running sample of the code here.

Click here for an even better method under a special scenario.