How do you find the kth largest element in an array, and what are the options?
There are three main ways to do it, and they differ in how much time and memory they use.
The first way is to sort the array and take the value at the right position. It is the easiest to write and it is the one to use when you only have to do it once.
def kth_largest(values, k):
ordered = sorted(values, reverse=True)
return ordered[k - 1]
data = [3, 2, 1, 5, 6, 4]
print(kth_largest(data, 2)) # 5
The second way is to use a heap that only holds k items. That is O of n log k for the time and O of k for the space, and it is the right choice when you want the k biggest items rather than one value.
The third way is quickselect, which throws away half of the array every round. That is O of n on average for the time, and it is the fastest of the three when you only need one value.
the method the time the space gives you
---------------- --------------- ---------- ----------------
sorting O(n log n) O(n) one value
a heap O(n log k) O(k) the k biggest
quickselect O(n) on average O(1) one value
And the choice comes down to two questions. Do you need one value or the whole top group? And does the array have to stay in its original order?
And there is one detail about the position. The kth largest is at position k minus one in the list that has been sorted from the largest end, because the positions in a list start at zero. And it is the same value as the position n minus k in a list sorted the other way, which is how some of the code is written.
So the rule to remember is this. Sort it when it is a one-off, use a heap when you want the top group, and use quickselect when you want one value and the array is big.
The next two questions in this topic show the heap and the quickselect.