Dashboard/Coding patterns/08. Top K Elements

CODING PATTERNS · LESSON 8 OF 28 · 59 MIN VIDEO · 18 PROBLEMS

Top K Elements

Module Progress (0 / 18 Problems Solved)0%
Coding patterns Track (0 / 28 Modules) · Overall 0/80 (0%)0%
⌁

Narrated HD Video Lesson (59 min) · Pro

Pattern Guide + Problem #01 + Checkpoint Quiz #1 are unlocked free below (no login required). Unlock all 80 HD video lessons and all 540 Python problems — or watch our two free sample video lessons first.

PATTERN STUDY GUIDE

Top K Elements — How the Pattern Works

The Top K Elements pattern uses a binary heap (priority queue) to select the k largest, smallest, or most frequent items—or to repeatedly extract and update a dynamic extremum—without fully sorting the input. When tracking the k largest elements, a min-heap bounded at capacity k maintains the invariant that heap[0] holds the smallest (weakest) of the k best candidates seen so far, allowing incoming values <= heap[0] to be discarded in O(1) time and replacements to execute in O(log k) time (symmetrically, a max-heap of size k tracks the k smallest elements). This eliminates redundant ordering among discarded elements, reducing full-sort O(n log n) passes to O(n log k) time and O(k) space, and accelerating k repeated extremum updates from O(n * k) linear scans to O(n + k log n).

WHEN TO USE THIS PATTERN
  • The prompt asks for the k largest, k smallest, k closest, or kth ranked element in a static array or an unbounded data stream.
  • You need the k most or least frequent elements after counting occurrences in a hash map, or must greedily interleave high-frequency items subject to an adjacency cooldown.
  • An objective combines an additive term and a bottleneck term—such as (sum of k values) * (minimum efficiency) or (max wage-to-quality ratio) * (sum of k qualities)—allowing you to sort by the bottleneck and maintain a size-k heap over the sum.
  • A greedy simulation repeatedly extracts the current global minimum or maximum, mutates it (e.g., ceiling division, increment, or multiplication), and reinserts it across k operations.
  • You need the top k or kth best value from an implicitly ordered combinatorial space (e.g., O(n^2) pair sums, O(2^n) subsequence sums, or k sorted lists) where each popped state expands O(1) immediate frontier neighbors.
COMMON INTERVIEW PITFALLS
  • Inverting heap polarity: using a max-heap of size k to find the k largest elements evicts the largest values and retains the k smallest; always pair k largest with a min-heap and k smallest with a max-heap.
  • Tuple comparison crashes or reversed tie-breakers in heapq: Python compares tuples left-to-right, so when negating keys (-priority, idx, item), verify that tie-breaker fields are comparable and have the intended sign (e.g., positive idx to prefer smaller indices on ties).
  • Missing deduplication for distinct ranks or shared frontier neighbors: distinct-rank queries (such as Third Maximum Number) and 2D index expansions ((i + 1, j) vs. (i, j + 1)) push duplicate entries unless guarded by a synchronized hash set.
  • Desynchronized auxiliary state on eviction: when tracking a running sum or membership set alongside a bounded heap, every heappop/heapreplace must update the sum (accounting for negated values) or remove the evicted key from the set.
  • Applying modular arithmetic before comparison: in optimization problems like Maximum Performance of a Team or Maximum Product After K Increments, track exact values (or heap ordering) during the algorithm and take modulo 10^9 + 7 only when computing the final return value.
Bounded Min-Heap of Size K (K Largest / Kth Largest)Selecting the k largest values or the kth largest threshold in O(n log k) time and O(k) space by keeping the weakest retained element at heap[0].
import heapq

def top_k_largest(nums, k):
    heap = []
    for num in nums:
        if len(heap) < k:
            heapq.heappush(heap, num)
        elif num > heap[0]:
            heapq.heapreplace(heap, num)
    return heap  # heap[0] is the kth largest
Bounded Max-Heap via Negation (K Smallest / K Closest)Selecting the k smallest keys in Python's min-heap heapq by negating priorities so the largest retained key sits at heap[0] for eviction.
import heapq

def top_k_smallest(items, k, key_fn):
    heap = []
    for item in items:
        key = key_fn(item)
        heapq.heappush(heap, (-key, item))
        if len(heap) > k:
            heapq.heappop(heap)
    return [item for _, item in heap]
Dynamic Extremum Simulation (Heapify + K Updates)Repeatedly extracting, transforming, and reinserting the minimum or maximum element across k greedy steps in O(n + k log n) time.
import heapq

def apply_k_updates(nums, k, transform):
    heap = [(num, i) for i, num in enumerate(nums)]
    heapq.heapify(heap)
    for _ in range(k):
        val, idx = heapq.heappop(heap)
        nums[idx] = transform(val)
        heapq.heappush(heap, (nums[idx], idx))
    return nums
Best-First Frontier Expansion (Top K Combinations)Enumerating the k best states from sorted inputs in O(k log k) heap work by expanding only adjacent index pairs from each popped state.
import heapq

def k_best_pair_sums(a, b, k):
    heap = [(-(a[0] + b[0]), 0, 0)]
    seen, result = {(0, 0)}, []
    while len(result) < k:
        neg_sum, i, j = heapq.heappop(heap)
        result.append(-neg_sum)
        for ni, nj in ((i + 1, j), (i, j + 1)):
            if ni < len(a) and nj < len(b) and (ni, nj) not in seen:
                seen.add((ni, nj))
                heapq.heappush(heap, (-(a[ni] + b[nj]), ni, nj))
    return result
🔒 PRO PROBLEMTarget: O(n log n) time · O(n) space

17. Least Number of Unique Integers after K Removals

Pattern Trigger: spend a budget on the cheapest first → min heap

Problem #01 of every pattern lesson is unlocked free outside the paywall. Unlock all 540 Python 3.14 problems, step-by-step solution editorials, and 80 narrated HD video lessons with Monthly ($69), 3-Month ($149), or Annual ($299) access — or 50% off for verified university students.

Pattern Checkpoint Quizzes

CHECKPOINT QUIZ #1

You want the five smallest of a million numbers, but you can only keep five in memory. Which do you use?