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)
Recommended Posts
- Find the Largest and Smallest Number in Unsorted Array – O(n)
- 2 Ways to Find the Duplicates in Array in O(n) time
- Find Numbers Repeated in Array in O(N) time without using Collections
- Running time in Big O notation for Java Arrays Algorithms
- Find Second Largest Element in an Unsorted Array – O(n)
- Program to reverse a string or word
- Efficient sorting mechanism for Unsorted Array – List Insertion Sort
- Find all possible combinations of numbers to print given sum