Is it possible to delete duplicates from a sorted array in $O(\log N)$ time and $O(1)$ space?
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
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
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
1 _ _ 4 4 _ 6
There's our duplicate, in
O(log n) time and
O(1) (extra) space.
Not possible in O(logn) time and O(1) space here's the link which may solve your problem