kth smallest element out of an non-unique sorted array

Question

This is probably a Microsoft interview question.

Find the kth smallest element (ignoring duplicates) out of an sorted array.
[EDIT]: The array may contain duplicates(not specified).

Thought a bunch of times, but still questioning myself: Does there still exist a better solution?

Approach 1:

Take a max heap & insert first k unique elements[can be easily checked]. Heapify the heap.
Now, when a new element is smaller than the head of the heap,replace head with this new element heapify it. At the last, the head of the heap indicates kth smallest element if size of the heap is k else kth smallest element doesn't exist.

Time complexity: O(NlogK)
Space complexity: O(K)

Approach 2[A better approach]:

The elements may be duplicated right. So, check for unique elements by comparing with its previous elements & stop if unique variables found so far counts to k.
Time complexity: O(N)
Space complexity: O(1)

Approach 3[A better approach(may be)]:

A modified version of quick sort partition algorithm can also be used. But possibly it will lead to a worst case as the array is already sorted.
here two questions arise:
1. Does it work if the array contain duplicates?
2. Would it be better than my second apporach?

---

I was wondering that does there exist any O(logn) solution?

Answer 1

Here's an O(kLogN) solution:

Using a variation of Binary Search to find the last occurrence of a given value,

1. Get 1st value - O(1).
2. Search for last occurrence of this value O(logN), then look at next element to get 2nd value - O(1).
3. Repeat until kth value is found.