Remove duplicates in an integer array using additional data structure
  • timecomplexity
  • array
  • searching
  • remove
  •   
  • Posted: 1 year ago
  • Updated: 2 months ago
  • Edit
  • answers (1)
  • views (72)

Can you improve the time complexity of Remove duplicates in an integer array using any additional data structure?


Posted Answers

The running time of the algorithm to find duplicates in an array can be improved to linear from linearithmic by using a Hash Table. The algorithm works as :


  • Create an empty Hash Table.
  • Take the first element of the array and check whether it is in the Hash Table. If not, put the element in the Hash Table. If yes, return the element.
  • Repeat the above step for all the elements of the array.

Time complexity = \( O(n) \), space complexity = \( O(n) \).

public int removeDuplicatesWithDataStructure(int[] array){

/* Array length zero - no duplicate */
if(array.length == 0)
return 0;

/* Create the Hash Table */
Map myMap = new HashTable();

/* Iterate through the array and check for the duplicates */
for(int i = 0; i < array.length; i++) {

/* Boolean variable to store whether the element is the HashTable */
boolean isExist = myMap.containsValue(array[i]);

/* When the element does not exist in the HashTable */
if(isExist == false)
myMap.put("array[i]", array[i]);
/* For duplicates */
else
return array[i];
}
}

You need to Sign In to post your solution.