Description
Return the kth largest array element, counting repeated values separately. Assume 1 <= k <= the array length.
Solution
import heapq
def find_kth_largest(nums, k):
heap = []
for value in nums:
heapq.heappush(heap, value)
if len(heap) > k:
heapq.heappop(heap)
return heap[0]Examples
Example 1
- Input
[[3,2,1,5,6,4],2]- Output
5
6 is first largest and 5 is second.
Example 2
- Input
[[3,2,3,1,2,4,5,5,6],4]- Output
4
The two 5s each occupy a rank.
Example 3
- Input
[[-1],1]- Output
-1
The only value is the first largest.
Approach
Keep a min-heap of the largest k elements while scanning. When it exceeds k, discard its smallest element. The remaining minimum has rank k from the top.
Time & space
O(n log(k + 1)) time and O(k) auxiliary space, where n is the array length.