Remove duplicates in an integer array
  • Posted: 1 year ago
  • Updated: 2 months ago
  • Edit
  • answers (1)
  • views (112)

You are given an array of random integers. How will you remove duplicates without using any additional data structure?


Posted Answers



  • Sort the array.
  • Take two pointers. A subarray will be created with all unique elements stating from \( 0 \) to the first pointer (The first pointer points to the last index of the subarray). The second pointer iterates through the array from \( 1 \) to the end. If the numbers referred by two pointers are different (duplicate numbers found), we pad the number from back to head.

Time complexity calculation :
Time to sort the array = \( O(nlogn) \).
Time to remove duplicates = \( \theta(n) \).
\( \therefore \) Overall Time complexity = \( O(nlogn) \).


public int removeDuplicatesW/ODataStructure(int[] array){

int j = 0;

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

/* Sort the array */
Arrays.sort(array);

for(int i = 1; i < array.length; i++) {
if(array[i] != array[j]) {
j++;
array[j] = array[i];
}
}
return j + 1;
}

You need to Sign In to post your solution.