Given an array numbers, how do we write a function checkDuplicates() which returns true if the array has at least one element repeated; returns false if all the elements are unique.

We discuss three different implementations of this function with various time and space complexities.

**Method-1: Naive approach**

This approach checks every possible pair in the array to see if there are any duplicates. This is exhaustive search and we can find the answer in O(n^{2}) time. Because there are n(n-1)/2 possible pairs for an array of size n.

Time complexity: O(n^{2})

Space complexity: O(1)

The following is the C++ function which implements this approach.

` `

bool checkDuplicates( int array[], int n)

{

int i,j;

for( i = 0; i < n; i++ )

{

for( j = i+1; j < n; j++ )

{

if( array[i] == array[j] )

return true;

}

}

return false;

}

**Method-2: Sorting Approach**

First sort the array using any sort which runs in O(n log n) time ( Quick sort/ Heap sort/ Merge sort).

Then all the duplicate elements comes together. Then simply compare all the adjacent elements to see if there are any duplicates.

Time complexity: O(n log n)

Space complexity: O(1)

The following is the C++ function which implements this approach.

bool checkDuplicates( int array[], int n)

{

std::sort( array, array+n);

int i;

for( i = 0; i < n-1; i++)

{

if( array[i] == array[i+1] )

return true;

}

return false;

}

**Method-3: Set/HashTable approach**

Use a data structure like a Set or a Hash Table which keeps track of the elements. When trying to insert into these data structures, we can see if the element already exists; If the element already exists in the data structure, we say that the array has duplicates.

Time complexity: O(n)

Space complexity: O(n)

The following is the __ Java__ function which implements this approach.

public static boolean checkDuplicates(int [] array)

{

HashSet<Integer> hSet = new HashSet<Integer>();

for( int i = 0; i < array.length; i++ )

{

if( !hSet.add(array[i]) )

return true;

}

return false;

}