Kth Largest Element
Find the Kth largest element in an unsorted array efficiently.
Top K Elements
Ready
Find Top 3 Elements
See the Logic in Motion
Stop memorizing code. Unlock the full interactive visualizer to master the logic step-by-step.Intuition
We could sort the entire array and pick the element at index N-K, but that takes O(N log N) time.
Using a Min-Heap of size K, we can iterate through the array once. The heap essentially acts as a filter, keeping only the "K largest elements seen so far". The smallest of these elite elements (the root) is exactly the Kth largest overall.
Concept
Algorithm:
- Initialize an empty Min-Heap.
- Iterate through every number `x` in the array.
- Push `x` into the heap.
- If heap size > K, pop the minimum element (remove the weakest of the "top" candidates).
- After checking all elements, the heap root is the answer.
How it Works
The visualizer below shows the heap updating as numbers stream in.
- Green Nodes: The K largest elements currently tracked.
- Red Action: When a new element enters, if it's smaller than the current minimum, it might be rejected (or force an eviction).
- Result: Start with [3, 2, 1, 5, 6, 4] and K=2. The heap evolves: [3] -> [2,3] -> [2,3] -> [3,5] -> [5,6] -> [5,6]. Answer 5.
Step-by-Step Breakdown
1. Create `MinHeap`.
2. Loop `x` in `nums`.
3. `heap.push(x)`.
4. If `heap.size() > K`: `heap.pop()`.
5. Return `heap.peek()`.
When to Use
- Finding median in a stream.
- Top K frequent words/numbers.
- Near-sorted array sorting.
When NOT to Use
- When K is very small (K=1, just linear scan).
- When K is very large (K=N, just standard sort).
How to Identify
"Return the Kth largest...", "Find top K..."
Stop Guessing, Start Mastering.
Build the FAANG intuition. Master this pattern with optimized implementations, visual dry runs, and our curated collection of high-yield problems.