# 2 Ways to Find the Duplicates in Array in O(n) time

Given an input array of integers, your goal is to find the duplicates present in the array in an effective way using Java Collections HashSet and HashMap. Note, you need to achieve this in O(n) time i.e., you should be able to find the results by traversing through the array only once.

## Algorithm 1 – Using HashSet

```1) Create a HashSet which can allow us to add elements of type Integer.
2) Iterate through input array.
3) Check if you can add the current element to the Set using add() function, if not then it is already present.
4) Print the element as duplicate if it is already present in the Set.```

## Example 1: Find the duplicates using HashSet

```package com.sneppets.dsalgo.examples;

import java.util.HashSet;
import java.util.Set;

/**
* Program to find duplicates in array in O(n) time
* using collections - HashSet
* @author sneppets.com
*/
public class DuplicatesInArrayHashSet {

public static void main(String[] args)
{
int inArray[] = {2, 4, 1, 7, 3, 5, 1, 3};
int arraySize = inArray.length;
findDuplicates(inArray, arraySize);
}

private static void findDuplicates(int[] inArray, int arraySize) {

//Create a HashSet which can allow us
//to add elements of type Integer
Set<Integer> hashSet = new HashSet<Integer>();
//Iterate through input array
for(int number: inArray)
{
//Check if you can add the current element to the Set,
//if not then it is already present
{
//Print the element as duplicate
//if it is already present in the Set
System.out.println(number + " is duplicate element");
}
}

}

}```

Output

```1 is duplicate element
3 is duplicate element
```

Time Complexity – Single Traversal – O(n)

Space Complexity – O(1)

Now let us see the second way to find duplicates using HashMap. Below is the algorithm for the same.

## Algorithm 2: Using HashMap

```1) Create a Hashmap of Integer Key and Value Pair
2) For each loop: Iterate through the input array, and for every element check whether it is present in the HashMap using containsKey() function.
3) If the current element is present in HashMap already, then print that element is duplicate.
4) If the current element is not present in HasMap already, then put it in HashMap using put() function.```

## Example 2: Find the duplicates using HashMap

```package com.sneppets.dsalgo.examples;

import java.util.HashMap;
import java.util.Map;

/**
* Program to find duplicates in array in O(n) time
* using collections - HashMap
* @author sneppets.com
*/
public class DuplicatesInArrayHashMap {

public static void main(String[] args)
{
int inArray[] = {2, 4, 1, 7, 3, 5, 1, 3};
int arraySize = inArray.length;
findDuplicates(inArray, arraySize);
}

private static void findDuplicates(int[] inArray, int arraySize) {

//create a HashMap of Integer Key and Value Pair
Map<Integer, Integer> map = new HashMap<Integer, Integer>();
// Iterate through input array
for(int i: inArray)
{
//if the map contains the current element already
if (map.containsKey(i))
{	//print that, the current element is duplicate
System.out.println(i + " is duplicate element");
}
else
{
//put it in HashMap using put() function.
map.put(i, i);
}
}

}

}```

Output

```1 is duplicate element
3 is duplicate element```

Time Complexity – Single Traversal – O(n)

## Recommended Posts

### Reference 