• 0

Remove duplicates in a sorted integer array
  • sortedarray
  • array
  • searching
  • remove
  • timecomplexity
  •   
    subscribe
  • Posted: 7 years ago
  • Updated: 6 years ago
  • Edit
  • answers (1)
  • views (5041)

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


Posted Answers

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

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.