ContainDuplicates

Problem statement

Given an array of integers, find if the array contains any duplicates. Your function should return true if any value appears at least twice in the array, and it should return false if every element is distinct.

Link to GitHub :Code

Solution

This problem seems trivial, so lets try different approaches to solve it:

Time complexity: O(N^2), memory: O(1)

The naive approach would be to run a iteration for each element and see whether a duplicate value can be found: this results in O(N^2) time complexity.

public class ContainsDuplicate {
 //Using trvial method
 /*
  * Time complexity: O(N^2), memory: O(1)
  */
 public static Boolean getTrivial(int [] arr)
 {
  //Iterate through the array
  for(int i = 0; i < arr.length; i++) {
            for(int j = i + 1; j < arr.length; j++) {
                if(arr[i] == arr[j]) {
                    return true;
                }
            }
        }
        return false;
 }
 //Here we first sort than we know that duplicates should be next to each other
 //O(N lg N), memory: O(1) 
 public static Boolean getSortandFind(int [] arr)
 {
  //Here we sort the array
  Arrays.sort(arr);
  //Iterate through the array
  for(int i = 0; i < arr.length; i++) {
                if(arr[i] == arr[i+1]) {
                    return true;
                }
            }
         return false;
 }
  //Time complexity: O(N), memory: O(N)
 public static Boolean getHashSet(int [] arr)
 {
  //If you make any variable, It will be constant.
    final  Set<Integer> distinct = new HashSet<Integer>();
  //Iterate through the array
  for(int i=0;i<arr.length;i++)
  {
   if(distinct.contains(arr[i]))
   {
    return true;
   }
   distinct.add(arr[i]);
  }
  
  return false;
 }
 
 //Using Hash Map
 public static Boolean get(int [] arr)
 {
  Map<Integer,Integer> map = new HashMap<Integer,Integer>();
  
  //Iterate through the array
  for(int i=0;i<arr.length;i++)
  {
   if(map.containsKey(map.get(arr[i])))
   {
    return true;
   }
   map.put(arr[i], arr[i]);
  }
  
  return false;
 }

}

Trivial method iteration

Iteration { 3, 2, 8, 10,20,2 }

Outer loop
/**
1st iteration
**/
3==2
/**
2nd iteration
**/
3==8
/**
3rd iteration
**/
3==10
/**
4th iteration
**/
3==20

/**
5th iteration
**/
3==2

inner loop

Outer loop
/**
1st iteration
**/
2==2  return
/**
2nd iteration
**/
3==8
/**
3rd iteration
**/
3==10
/**
4th iteration
**/
3==20

/**
5th iteration
**/
3==2