Kth Largest Element
LeetCode 215 • Medium • Heaps
Input: nums = [3, 2, 1, 5, 6, 4], k = 2 → Output: 5
Min-heap of size k: keep k largest. Pop smallest when heap exceeds k. Return heap[0].
TimeO(n log k)n pushes, heap size k
SpaceO(k)min-heap size
Heap: []
Pops: 0
Ready
Press Play. Min-heap of size k: push each num, pop when len>k. heap[0] is kth largest.
TimeO(n) avgquickselect
SpaceO(n) worstcall stack
3
Practice until you don't need to look. The green highlights are the nuances to burn into memory.
PATTERN ▸ Min-heap of size k O(n log k) · O(k)
① INIT
heap = []
② LOOP
for num in nums: heappush(heap, num)
if len(heap) > k: heappop(heap)
③ RETURN
return heap[0]
▼ your implementation ▼
Verify your solution:
Practice until you don't need to look. Quickselect: partition, recurse left or right.
PATTERN ▸ Pivot, partition, recurse O(n) avg · O(1)
① PARTITION
pos = partition(nums, ...)
② COMPARE & RECURSE
if pos == k-1: return nums[pos]
elif pos < k-1: recurse right
else: recurse left
▼ your implementation ▼
Verify your solution: