# 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)`