k-th Smallest Number In List

Computer Science Level 2

One way to find to find the $k$ th smallest element in a list is to first sort the list, and then take the $k$ th element in the sorted list.

However, sorting has a minimum worst-case runtime of $O(n\log(n)).$ Is it possible to find the $k$ th smallest element with worst-case runtime $O(n)?$

Bonus: Prove your answer!

No Yes

2 solutions

Vijay Kumar
Jan 20, 2016

No need to worry...just hash all the elements in an array. For rest, look at the below python code.

def kthsmallest(array,k) :
    hash = [0]*(10**7+1)
    for i in array :
        hash[i] += 1
    tempk , i = 1 , 0
    while tempk <= k :
         tempk += hash[i]
         i += 1
         if i>10**7 : break 
    return i if i<10**7 else -1

Here I considered that the array has duplicates. This just takes O(n) in the worst case, which I fixed 10^7 is the upper bound. This won't work if the array contains negative numbers.

Fredrik Meyer
Oct 12, 2015

I'm not completely sure about this solution, so if you see any mistakes, please tell. To find the kth smallest element in a list of k elements, we just find the maximum element. This has runtime O(n) (we use just a single while loop). We can partition our list into k+1 sublists, find the max in each of them, to get a list of candidates. The kth smallest element is then the minimum of this list of maxima. We just do several O(n) runtimes, so the total is still O(n).

k-th Smallest Number In List

2 solutions

0 pending reports