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)

by nikoo28
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;
		//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;
	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.

0 comment

You may also like

Enclose codes in [code lang="JAVA"] [/code] tags

This site uses Akismet to reduce spam. Learn how your comment data is processed.

This website uses cookies to improve your experience. We'll assume you're ok with this, but you can opt-out if you wish. Accept Read More