**Objective: **Given an array of integers, find out duplicates in it.

**Example:**

int [] a = {4, 6, 2, 1, 2, 5}; Output: Array has duplicates : 2 int a [] = {1, 6, 5, 2, 3, 3, 2}; Output: Array has duplicates : 2 , 3

**Approach:**

**Naive approach: **Use 2 loops. Check each element in the array with all other elements in the array and check if it has the same value.

Time Complexity : O(n^2) Space Complexity: O(1)

**Code:**

import java.util.Arrays; | |

public class CheckDuplicatesUsingTwoLoops { | |

public void hasDuplicates2ForLoops(int [] arrA) { | |

for (int i = 0; i < arrA.length; i++) { | |

for (int j = i+1; j < arrA.length; j++) { | |

if(arrA[i]==arrA[j]){ | |

System.out.println("Array has duplicates : " + arrA[i]); | |

} | |

} | |

} | |

} | |

public static void main(String[] args) { | |

int a [] = {1, 6, 5, 2, 3, 3, 2}; | |

new CheckDuplicatesUsingTwoLoops().hasDuplicates2ForLoops(a); | |

} | |

} |

**Sorting approach:** Sort the array, this will bring all the duplicates together if present. Now navigate the array and check the adjacent elements to check for duplicates.

Time Complexity : O(nlogn) Space Complexity: O(n) by using merge sort.

**Code:**

import java.util.Arrays; | |

public class CheckDuplicatesUsingSorting { | |

public void hasDuplicatesUsingSorting(int [] arrA) { | |

Arrays.sort(arrA); | |

for (int i = 0; i < arrA.length–1; i++) { | |

if(arrA[i]==arrA[i+1]){ | |

System.out.println("Array has duplicates : " + arrA[i]); | |

} | |

} | |

} | |

public static void main(String[] args) { | |

int a [] = {1, 6, 5, 2, 3, 3, 2}; | |

new CheckDuplicatesUsingSorting().hasDuplicatesUsingSorting(a); | |

} | |

} |

**Better Solution :** Use Hash map. Store the count of each element of array in a hash table and later check in Hash table if any element has count more than 1. ( Similar approach is used in problem – Find the first non repeating character in a given string

Time Complexity : O(n) and Space Complexity: O(n).

**Code:**

import java.util.Arrays; | |

import java.util.HashMap; | |

public class CheckDuplicatesUsingHashMap { | |

public void hasDuplicatesUsingMap(int [] arrA){ | |

HashMap<Integer, Integer> map = new HashMap<>(); | |

for (int i = 0; i <arrA.length ; i++) { | |

if(map.containsKey(arrA[i])){ | |

System.out.println("Array has duplicates : " + Math.abs(arrA[i])); | |

}else{ | |

map.put(arrA[i], 1); | |

} | |

} | |

} | |

public static void main(String[] args) { | |

int a [] = {1, 6, 5, 2, 3, 3, 2}; | |

new CheckDuplicatesUsingHashMap().hasDuplicatesUsingMap(a); | |

} | |

} |

**Better Solution** (Conditional) : **O(n) time and O(1) extra space.**

- This solution works only if array has positive integers and all the elements in the array are in range from 0 to n-1 where n is the size of the array.
- Navigate the array.
- Update the array as for ith index :- arrA[arrA[i]] = arrA[arrA[i]]*-1 (if it already not negative).
- If is already negative, we have duplicates, return false.

**Note**:

- The code given below does not handle the case when 0 is present in the array.
- To handle 0 in array, while navigating the array, when 0 is encountered, replace it with INT_MIN and if INT_MIN is encountered while traversing, this means 0 is repeated in the array.

Similar approach used in problem : If array has all consecutive numbers.

**Code:**

public class CheckDuplicates { | |

public void hasDuplicates(int[] arrA) { | |

for (int i = 0; i < arrA.length; i++) { | |

//check if element is negative, if yes the we have found the duplicate | |

if (arrA[Math.abs(arrA[i])] < 0) { | |

System.out.println("Array has duplicates : " + Math.abs(arrA[i])); | |

} else { | |

arrA[Math.abs(arrA[i])] = arrA[Math.abs(arrA[i])] * –1; | |

} | |

} | |

} | |

public static void main(String[] args) { | |

int a[] = {1, 6, 5, 2, 3, 3, 2}; | |

new CheckDuplicates().hasDuplicates(a); | |

} | |

} |

**Output:**

Array has duplicates : 3 Array has duplicates : 2