Write a program to check if there are any duplicated elements in an array?

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

This is one of the simplest problems. One obvious solution to this is, exhaustively searching for duplicated elements in the array. That means, for each input element check whether there is any element with the same value. This we can solve by using two simple for loops. The code can be written as:-

//checks duplicate in an array arr[] of size
int checkDuplicatesBruteForce(int arr[], int size)
{
	//the flag to return
	int duplicate_exist = 0;

	int i,j;
	for(i = 0; i<size; i++)
	{
		for(j = i+1; j<size; j++)
		{
			if(arr[i] == arr[j])
			{
				//we have found a duplicate, change the flag
				//and break the loop. No need to check further.
				duplicate_exist = 1;
				break;
			}
		}
	}

	return duplicate_exist;
}

Time Complexity:- O(n²)
Space Complexity:- O(1)

Click here to find a better approach of solving the above problem.