Problem Statement
Kth Largest Element in an Array
You are given a list of numbers called nums and a number k. Return the kth largest number in the list. This means: if you sorted the list from biggest to smallest, which number would be in the kth spot? It is the kth largest by value, not the kth different value. So if a number repeats, each copy still counts.
Signals to notice
Brute force first
Sort the entire array and return nums[n-k]. Full sort when you only need one element. It is a fair place to begin because it matches the surface of the question, yet it does not capture the deeper structure that makes the problem simpler.
The key insight
Min-heap of size k: the heap's minimum is always the kth largest. Process all elements — if larger than heap min, replace. Or use Quickselect for average. Once you hold onto the right piece of information from moment to moment, the problem feels less like trial and error and more like following a shape that was there all along.
Trace it on nums=[3,2,1,5,6,4], k=2
push 3 -> heap{3}, size 1 <= 2, keep
push 2 -> heap{2,3}, size 2 <= 2, keep
push 1 -> heap{1,2,3}, size 3 > 2, pop min(1) -> heap{2,3}
push 5 -> heap{2,3,5}, size 3 > 2, pop min(2) -> heap{3,5}
push 6 -> heap{3,5,6}, size 3 > 2, pop min(3) -> heap{5,6}
push 4 -> heap{4,5,6}, size 3 > 2, pop min(4) -> heap{5,6}
return heap[0]=5 (kth=2nd largest)What must stay true
A min-heap of size k contains the k largest elements. The smallest of those (the heap top) is by definition the kth largest overall. When you keep that truth intact, each local choice supports the larger solution instead of fighting it.
Shape of the loop
heap = empty min-heap
for num in nums:
push num onto heap
if size(heap) > k: pop smallest
return top(heap) # heap min = kth largestPseudocode only — the full worked solution lives in the Solution tab.
Easy way to go wrong
Using a max-heap of all n elements — that's which is worse than the min-heap approach for large n and small k. The fix is usually to return to the meaning of each move, not just the steps themselves.