kth largest element in an array

🏠

This problem is tricker 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:

 1 from bisect import insort, bisect_left
 2 
 3 
 4 def 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 
18 print(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)