Remove the Duplicates from Unsorted Array in O(n) Time

Given an input array of integers, your goal is to remove the duplicates present from an unsorted array in an effective way. 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) create a HashMap of Integer Key and Value Pair
2) Iterate through input array
2.1) If the map contains the current element already,
then it is a duplicate and continue traversing the array.
2.2) Else put the current element in map using put() function.
3) Print map values using map.values() function```

Solution to remove the duplicates

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

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

/**
* Program to remove duplicates from Unsorted Array in O(n) time
* @author sneppets.com
*/
public class RemoveDuplicatesUnsortedArray {

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

private static void removeDuplicates(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 element: inArray)
{
//if the map contains the current element already
if (map.containsKey(element))
{	//print that, the current element is duplicate
System.out.println(element + " is duplicate element");
}
else
{
//put it in HashMap using put() function.
map.put(element, element);
}
}
//print map values
System.out.println(map.values());
}
}```

Output

```1 is duplicate element
3 is duplicate element
[1, 2, 3, 4, 5, 7]```

Time Complexity – Single Traversal- O(n)

Subscribe
Notify of