Kth Largest Element
Medium · rating 1250 · sorting, arrays
The first line contains n and k. The second line contains n integers. Print the k-th largest value (duplicates count).
Constraints: 1 ≤ k ≤ n ≤ 105
Editorial
Approach
The simplest correct answer sorts descending and takes index k-1 — O(n log n). To do better, keep a min-heap of the k largest values seen so far: push each element, and pop when the heap grows beyond size k. The heap's smallest element is then the k-th largest overall.
import heapq
h = []
for x in nums:
heapq.heappush(h, x)
if len(h) > k: heapq.heappop(h)
return h[0]Complexity
Heap: O(n log k) time, O(k) space. Quickselect averages O(n) time.