Wednesday, September 11, 2013

Check if an array has duplicate numbers

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(n2) time. Because there are n(n-1)/2 possible pairs for an array of size n.

Time complexity: O(n2)
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;
    }