Remove duplicates in a sorted integer array
  • sortedarray
  • array
  • searching
  • remove
  • timecomplexity
  •   
  • Posted: 4 years ago
  • Updated: 3 years ago
  • Edit
  • answers (1)
  • views (3001)

Can you improve the time complexity in Remove duplicates in an integer array if the input array is sorted?


Posted Answers

We can improve the time complexity to find the duplicates in an array when the input array is sorted. Let us assume that the numbers are increasing by \( 1 \) and starting from \( 0 \). We can use modified binary search to find the duplicates.


  • Find the middle element of the input array and compare it with its index.
  • If they are same, the duplicate element(s) will be at the upper half of the array.
  • Otherwise, it will be at the lower half of the array.

Time complexity = \( O(logn) \).

public static int findDuplicates(int[] array) {

int low = 0;
int high = array.length - 1;

while (low < = high) {
int middle = (low + high);
int middleValue = array[middle];

if (middleValue == middle)
low = middle + 1;
else
high = middle - 1;
}
return high;
}

You need to Sign In to post your solution.