• 0

Remove duplicates in an integer array using additional data structure
  • timecomplexity
  • array
  • searching
  • remove
  •   
    subscribe
  • Posted: 7 years ago
  • Updated: 6 years ago
  • Edit
  • answers (1)
  • views (6178)

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


Posted Answers

  • Posted: 7 years ago
  • Updated: 7 years ago
  • 0 0
  • Edit

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.