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.

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

Time complexity: O(n

Space complexity: O(1)

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

Time complexity: O(n log n)

Space complexity: O(1)

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

Time complexity: O(n)

Space complexity: O(n)

The following is the

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

**Method-1: Naive approach**

^{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.

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.

Space complexity: O(n)

The following is the

__function which implements this approach.__*Java*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; }