Archived

kth largest element in an array

An old note — I haven't updated it since I wrote it.

This problem is trickier than it sounds. It's obviously not hard to solve, but there are many different solutions, with many different time and space tradeoffs.

Here's my solution:

 1from bisect import insort, bisect_left
 2
 3
 4def kth_largest(A, k):
 5    items = []
 6    for a in A:
 7        if not items or a > items[-1]:
 8            items.append(a)
 9        elif a > items[0]:
10            ind = bisect_left(items, a)
11            if items[ind] != a:
12                insort(items, a)
13        if len(items) > k:
14            items.pop(0)
15    return items[0]
16
17
18print(kth_largest([1, 2, 4, 5, 4, 3, 5, 7, 8, 9, 7, 6, 5, 4, 4], 3))

Since items remains sorted, we can use bisect.insort to insert the new item in sorted order. bisect_left also performs a binary search for the membership test; this is more optimal to doing a in items which is linear.

Time Complexity: O(nlogk)
Space Complexity: O(k)