remove the duplicates

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

Reference

guest
0 Comments
Inline Feedbacks
View all comments