Is it possible to delete duplicates from a sorted array in $O(\log N)$ time and $O(1)$ space?

  • 2
    $\begingroup$ Why do you think it should be possible in $O(\log n)$ time? $\endgroup$ Apr 20 '16 at 13:18
  • $\begingroup$ Related: cs.stackexchange.com/questions/54827/… $\endgroup$
    – Auberon
    Apr 20 '16 at 13:23
  • 4
    $\begingroup$ If the array was all one of the same element, it would take O(N) operations just to remove them. If we had to do sorting in O(logN) time then I guess we have to think of binary search. $\endgroup$
    – Riya K
    Apr 20 '16 at 13:43
  • 2
    $\begingroup$ @RiyaK Your comment proves that the thing you're asking for is impossible. $\endgroup$ Apr 20 '16 at 15:36
  • 1
    $\begingroup$ Please don't ask for "best", as "best" as subjective (everyone may have their own opinion about what's best and what qualities are most important -- ease of coding, efficiency, asymptotic performance, etc.). Instead, just list your requirements. $\endgroup$
    – D.W.
    Apr 21 '16 at 22:54

It is not possible to delete all duplicates from a sorted list faster than O(n) time unless you have some other information about the list. You have to look at each item at least one to see what value it has. If you do not do that, we could make two of the items you're not looking at duplicates of each other, and you would have no way of knowing, since you didn't look at those items.

One example of a special sorted list where you could find any constant number of duplicate items is one with all numbers [a,b] with some constant number of duplicated items. We can look at any two positions and figure out how many duplicates there are in between by comparing the numbers with their positions in the array.

Consider this list:

1 2 3 4 4 5 6

There's one duplicate element. By looking at 1 and 6 we know that there should be the numbers 1 2 3 4 5 6 in between them, but there's one slot too many between them, so there must be at least one duplicate. Continue by splitting the list in half by looking at the middle element, the first 4.

1 _ _ 4 _ _ 6

The first half has 4 items and by comparing the numbers at position 1 and position 4, we know that there cannot possibly be any duplicates there.

Between 4 and 6, however, we have 2 slots. Thus there must be a duplicate 4, 5 or 6.

1 _ _ 4 4 _ 6

There's our duplicate, in O(log n) time and O(1) (extra) space.

  • $\begingroup$ Apt solution for a very restricted version of te problem. $\endgroup$
    – Raphael
    Apr 22 '16 at 12:16

Not possible in O(logn) time and O(1) space here's the link which may solve your problem


Not the answer you're looking for? Browse other questions tagged or ask your own question.