All Patterns
🏆
mediumPattern #11
Top K Elements
Use a heap to track the K largest or smallest elements in O(n log k).
What is this pattern?
Instead of sorting the entire array (O(n log n)), a min-heap of size k keeps exactly the k largest elements seen so far. When the heap exceeds k, pop the smallest. The heap root is always the kth largest. For kth smallest, use a max-heap.
When to use it
- Finding kth largest or kth smallest element
- Top K frequent elements
- Merging K sorted lists
- Finding the median of a stream (two heaps)
- Keywords: "k largest", "k most frequent", "k closest"
Key Insight
Min-heap of size k → gives you k largest (root = kth largest). Max-heap of size k → gives you k smallest (root = kth smallest). Always ask: which end of the heap do I want to evict from?
Pro Content
The Java template and practice problems for this pattern are part of the Pro plan. Upgrade to unlock all patterns, 500+ problems, and Aria code reviews.
From ₹3,999 for a year · one-time, no auto-renewal