kth smallest element out of an non-unique sorted array

9
votes

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?

2
algorithmdata-structureslanguage-agnostic
Maybe I'm missing something, but isn't the "k-th smallest element of an sorted array" is just the k-th element of the array? The array is sorted... – kennytm
if the array is sorted, why not take the element at k-th position? – Sufian Latif
@KennyTM .. Aint that easy.. It can hav duplicates.. – bragboy
KennyTM, FlopCoder: {1,1,1,1,2,2,3,4,5,6}. Your algorithm incorrectly returns 1 for k = 3. – Nick
@Bragboy, ngmiceli: You didn't mention "unique elements" :) The default interpretation is to include duplicates, e.g. C++ says 1 is the correct answer for the 3rd smallest element. – kennytm

2 Answers

8
votes

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.
5
votes

There appear to be two different interpretations of k-th smallest element. I am assuming it means "the k-th smallest element, ignoring duplicates."

The best solution is O(n) time and O(1) space, as you describe in approach 2. We can prove this.

  • We cannot improve upon O(1) space (at least not in O-notation).
  • Consider an approach that runs in less than O(n). Such an approach must not consider each element in the array. Consider one such missed element. It it not known if this element is or is not a duplicate of the value previous to it or after it¹, and this information is required for asserting which value in the array corresponds to the k-th smallest.

¹ It is possible to infer the values of a arbitrarily long subsequence of a sorted array in the special case that two non-adjacent array elements have the same value: all of the interim elements must share that value. But this is not a typical case, so I'm ignoring it.