patternDSA/Top 'K' Elements
Core Pattern → Pattern 22

Top 'K' Elements

A size-k heap replaces full sorting. Push every element; evict when size exceeds k. heap[0] is always the kth largest. O(n log k) — only k elements ever compete.

Frequency:★★★★★
·~30 min·Beginner–Hard·14 problems
The Core Shock

Sorting for top-k = O(n log n). A size-k heap = O(n log k). When k≪n, this is a massive speedup.

sorted(nums)[:k]
O(n log n)
Sort 1,000,000 elements to get top 3. Wasted work on 999,997 numbers.
min-heap of size k
O(n log k)
Each insert/evict is O(log k). Only k elements ever compete. heap[0] = answer.

The heap acts as a tournament of k contenders. Every new number challenges the current weakest contender (heap[0] = the minimum). If the challenger wins, the weakest is evicted. After n comparisons, the k survivors are the global top k. The heap minimum is always the kth largest.

The k-Heap Trick

Which heap type depends on which end you're finding.

Top k LARGEST
Min-heap of size k

The min at heap[0] is the smallest of the k largest = kth largest overall. Push new element; if size > k, pop the min (weakest contender). Any new element smaller than heap[0] can't make top k.

heappush(h, num) if len(h) > k: heappop(h) # heap[0] = kth largest
Top k SMALLEST
Max-heap of size k

Negate values for Python max-heap. The max at heap[0] (negated) is the largest of the k smallest = kth smallest overall. Push; if size > k, pop the max (worst contender).

heappush(h, -num) if len(h) > k: heappop(h) # -h[0] = kth smallest

The 3-Step Framework

Two-line pattern covers 80% of top-k problems.

01
Push every element onto a size-k heap

For top k largest: use a min-heap. For top k smallest: use a max-heap (negate). For top k by custom key: heap stores (key, value) tuples. Push each element as you scan the input.

for num in nums:
    heapq.heappush(heap, num)  # or (-num) for max-heap
    if len(heap) > k:
        heapq.heappop(heap)        # evict weakest contender
The eviction happens when size EXCEEDS k (not equals k). After eviction, size is back to k. heap[0] is always the boundary element — the kth largest or smallest.
02
For frequency problems: count first, then heap

Top k frequent: Counter(nums) gives frequencies. Then push (freq, num) tuples onto a min-heap of size k. Evict tuples with lowest frequency. Result: the k entries with highest frequency remaining in the heap.

from collections import Counter
count = Counter(nums)
for num, freq in count.items():
    heapq.heappush(heap, (freq, num))
    if len(heap) > k:
        heapq.heappop(heap)
Heap sorts by first element of tuple. (freq, num) means frequency is the comparison key. The min-heap evicts the lowest-frequency element — exactly what we want.
03
For greedy problems: max-heap to always pick best

Rearrange string, scheduling tasks, connect ropes: use a max-heap (negate in Python). At each step, greedily pop the highest-priority element, use it, and push back with updated state. For cooldown constraints, hold elements in a queue before re-adding.

# Greedy: always pick most frequent
heap = [(-freq, ch) for ch, freq in Counter(s).items()]
heapq.heapify(heap)
while heap:
    freq, ch = heapq.heappop(heap)  # most frequent
    result.append(ch)
    # ... handle cooldown / re-push
heapq.heapify(list) builds a heap in O(n) — faster than n individual pushes. Use it when you have all elements upfront. Use individual pushes for streaming data.

Pattern Recognition

k + largest/smallest/frequent/closest = this pattern.

Use Top K Pattern When
"Find the k largest/smallest elements"
"Kth largest/smallest number"
"K closest points to origin"
"Top k most frequent elements"
"Kth largest element in a stream"
Connect ropes with minimum cost (always cheapest two)
"Sort characters by frequency"
Schedule tasks with cooldown (max-heap greedy)
Common Pitfalls
Using max-heap for top k LARGEST (should be min-heap — backwards!)
Evicting when size == k instead of size > k (off-by-one)
Forgetting to negate values when simulating max-heap in Python
Top k frequent: pushing (num, freq) not (freq, num) — wrong sort key
K closest: using sqrt distance (unnecessary) vs distance squared
Rearrange string: not holding previous char — placing same char twice
Scheduling tasks: forgetting the max() with len(tasks) — tasks may fill all frames
heapq.nlargest(k, nums) is O(n log k) but creates full sorted list — use for small n