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
			if(!hashSet.add(number))
			{
				//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);
			}
		}		
		
	}

}