Top K Elements

How It Works

The Top K Elements pattern avoids sorting the entire input (O(n log n)) when you only need K elements out of it. The core idea is to maintain a heap of size K as you scan the data once: for "K largest" problems, keep a min-heap of size K: any new element bigger than the heap's smallest gets swapped in, and the smallest gets evicted. For "K smallest" problems, do the mirror image with a max-heap.

// Kth largest element using a min-heap of size k.
// (JS has no built-in heap, so this uses a simple array-backed
// min-heap; swap in a real MinHeap/priority-queue class in production.)
function findKthLargest(nums, k) {
  const minHeap = [];

  const siftUp = () => {
    let i = minHeap.length - 1;
    while (i > 0) {
      const parent = (i - 1) >> 1;
      if (minHeap[parent] <= minHeap[i]) break;
      [minHeap[parent], minHeap[i]] = [minHeap[i], minHeap[parent]];
      i = parent;
    }
  };

  const siftDown = () => {
    let i = 0;
    const n = minHeap.length;
    while (true) {
      let smallest = i;
      const left = 2 * i + 1;
      const right = 2 * i + 2;
      if (left < n && minHeap[left] < minHeap[smallest]) smallest = left;
      if (right < n && minHeap[right] < minHeap[smallest]) smallest = right;
      if (smallest === i) break;
      [minHeap[i], minHeap[smallest]] = [minHeap[smallest], minHeap[i]];
      i = smallest;
    }
  };

  for (const num of nums) {
    minHeap.push(num);
    siftUp();
    if (minHeap.length > k) {
      minHeap[0] = minHeap.pop();
      siftDown();
    }
  }

  return minHeap[0];
}

Why a min-heap for "K largest"? Because the heap's root is always the smallest element currently in your top-K candidate set; it's the first one to evict the moment you find something bigger. By the time you've scanned the whole array, the heap holds exactly the K largest elements, and its root is the Kth largest.

When To Use It

Reach for the Top K Elements pattern when you spot any of these signals:

• The problem explicitly asks for the Kth largest, Kth smallest, or the top/closest K elements.
• You need frequency-based ranking (e.g., "the K most frequent elements/words") where you first build a frequency map, then reduce it to K entries with a heap instead of sorting all unique values.
• Fully sorting feels wasteful: if K is small relative to n, O(n log k) with a heap beats O(n log n) with a full sort.
• The input has existing partial structure you can exploit alongside a heap: a sorted matrix (each row/column already sorted) or multiple sorted arrays, where a heap tracks the next-smallest "frontier" candidate instead of merging everything.
• You need the K closest points/values to a target: distance-from-target is just another ranking key for the same heap-of-size-K technique.

If you need all elements in sorted order (not just K of them), a plain sort is simpler and just as fast asymptotically. Don't reach for a heap unless K is meaningfully smaller than n.

Time & Space Complexity

• Time: O(n log k): each of the n elements triggers at most one heap push and one conditional pop, and each heap operation costs O(log k) since the heap never grows past size k.
• Space: O(k): the heap only ever holds k elements at a time, independent of n (excluding any auxiliary frequency map, which is O(n) in the worst case for problems like Top K Frequent Elements).

Alternative Approaches

• Quickselect: for a single "find the Kth largest/smallest" query (not needing them in order, and not needing to support a stream), Quickselect achieves average O(n) time by partitioning around a pivot like quicksort but only recursing into the side that contains the Kth index. It's faster on average than the heap approach but has O(n²) worst case without care, and doesn't extend well to streaming input.
• Full sort: O(n log n), perfectly fine and simpler to write when K is close to n, or when n is small enough that the asymptotic difference doesn't matter in practice.
• Bucket sort by frequency: for "K most frequent elements" specifically, since frequency is bounded by n, you can bucket elements by their frequency count into an array of size n+1 and read off the top K buckets from the end; this achieves O(n) time, better than the O(n log k) heap approach, at the cost of O(n) extra space.

Common Mistakes

• Using a max-heap when you need a min-heap (or vice versa): the single most common mix-up in this pattern. For "K largest," you evict the smallest candidate, which means the heap you maintain is a min-heap; it's counterintuitive the first few times.
• Sorting the entire input when only K elements were asked for: it'll pass small test cases but defeats the point of the pattern and costs you the efficiency argument in an interview.
• Forgetting tie-breaking rules: "top K frequent" problems can have multiple valid answers when frequencies tie; read the constraints/examples carefully to see if a specific tie-break order is expected or if any valid set is accepted.
• Off-by-one on heap size checks: pushing before checking size, or checking >= k instead of > k, silently changes which K elements you end up keeping.
• Recomputing distance/priority repeatedly inside the heap comparator: for "K closest points" style problems, precompute the squared distance once per point (avoid unnecessary Math.sqrt, which is monotonic and unnecessary for comparison) rather than recalculating it on every heap operation.

Pattern Summary

Top K Elements is "maintain a heap of size K, evict the worst candidate as better ones arrive." Whenever a problem wants only K elements out of a much larger set (by value, frequency, or distance), this gets you there in O(n log k) without paying for a full sort, and it generalizes cleanly to streaming input where you don't have all the data upfront.