Check if array contains duplicates

Problem 
Given an array of n elements, check if it has duplicates

Solution
This problem is similar to following problem :

• Find the two repeating elements in a given array

We can use some of the method used there.

Method 1 - Brute force
Use two loops. In the outer loop, pick elements one by one and count the number of occurrences of the picked element in the inner loop.
This method doesn’t use the other useful data provided in questions like range of numbers is between 1 to n and there are only two repeating elements.

bool hasDuplicates(int arr[], int size)
{
  int i, j;
  printf(" Repeating elements are ");
  for(i = 0; i < size; i++)
    for(j = i+1; j < size; j++)
      if(arr[i] == arr[j])
        return true;
  return false;
}  

Time Complexity: O(n*n)
Auxiliary Space: O(1)

Method 2 - Use Count array (for hashing)
Traverse the array once. While traversing, keep track of count of all elements in the array using a temp array count[] of size n, when you see an element whose count is already set, print it as duplicate.
This method uses the range given in the question to restrict the size of count[], but doesn’t use the data that there are only two repeating elements.

bool hasDuplicates(int arr[], int size)
{
  int *count = (int *)calloc(sizeof(int), (size - 2));
  int i;
  printf(" Repeating elements are ");
  for(i = 0; i < size; i++)
  { 
    if(count[arr[i]] == 1)
      return true;
    else
     count[arr[i]]++;
  }   
  return false;
}  

Time Complexity: O(n)
Auxiliary Space: O(n)

Method 3 - Sorting the array and compare adjacent array

bool hasDuplicates(int arr[], int size)
{
  sort(arr);
  int i, j;
  printf(" Repeating elements are ");
  for(i = 0; i < size; i++)
    for(j = i+1; j < size; j++)
      if(arr[i] == arr[j])
         return true;
  return false;
}

Sorting takes O(n log n) time, but as they are integers we can use counting sort, which takes O(n) time.

Time complexity = O(n log n) OR O(n)

Time complexity = O(n log n)
Space Complexity = O(1)
Sorting takes O(n log n) time, and then comparing takes O(n) times.

Method 4 - Method of negation
As we are told that array of integers are from 1 to n, they are positive. For each element A[i], go to index A[i] , i.e. select array element A[A[i]] and negate it. Continue this process until you find some negative number.

Pseudocode

Traverse the array. Do following for every index i of A[].
{
  check for sign of A[abs(A[i])] ;
  if positive then
     make it negative by   A[abs(A[i])]=-A[abs(A[i])];
  else  // i.e., A[abs(A[i])] is negative
     this   element (ith element of list) is a repetition
}

Example: A[] =  {1, 1, 2, 3, 2}
i=0; 
Check sign of A[abs(A[0])] which is A[1].  A[1] is positive, so make it negative. 
Array now becomes {1, -1, 2, 3, 2}

i=1; 
Check sign of A[abs(A[1])] which is A[1].  A[1] is negative, so A[1] is a repetition.

i=2; 
Check sign of A[abs(A[2])] which is A[2].  A[2] is  positive, so make it negative. '
Array now becomes {1, -1, -2, 3, 2}

i=3; 
Check sign of A[abs(A[3])] which is A[3].  A[3] is  positive, so make it negative. 
Array now becomes {1, -1, -2, -3, 2}

i=4; 
Check sign of A[abs(A[4])] which is A[2].  A[2] is negative, so A[4] is a repetition.

Note that this method modifies the original array and may not be a recommended method if we are not allowed to modify the array.

bool hasDuplicates(int arr[], int size)
{
  int i;  
  
  printf("\n The repeating elements are");
   
  for(i = 0; i < size; i++)
  {
    if(arr[abs(arr[i])] > 0)
      arr[abs(arr[i])] = -arr[abs(arr[i])];
    else
      return true;
  }
  return false;         
}  

Note that solution works only for positive number, and for the ranged array of 0 to n-1 elements.