Top K Elements Pattern

When to Use Top K Pattern

Any problem asking for top/largest/smallest K elements is a heap problem. Key insight: maintain a heap of size K instead of sorting the entire array. Time complexity: O(n log k) vs O(n log n) for a full sort. When K is much smaller than n, the savings are significant.

The pattern applies wherever you need to track a running top-K set: streaming data, leaderboards, frequency analysis, and nearest-neighbor queries all follow this structure.

Kth Largest Element

Maintain a min heap of size K. After processing all elements, the root is the Kth largest. Counterintuitively, to find the largest K elements, you keep a min heap: this efficiently evicts elements that are too small.

function findKthLargest(nums: number[], k: number): number {
  const minHeap = new MinHeap()
  
  for (const num of nums) {
    minHeap.push(num)
    if (minHeap.size() > k) minHeap.pop()
  }
  
  return minHeap.peek()
}
// Maintain min heap of size k
// Root is the kth largest element

Top K Frequent Elements

Count frequencies with a hash map, then use a min heap keyed by frequency. Keep only the K most frequent entries.

function topKFrequent(nums: number[], k: number): number[] {
  const freq = new Map<number, number>()
  for (const num of nums) freq.set(num, (freq.get(num) || 0) + 1)
  
  const heap = new MinHeap<[number, number]>((a, b) => a[1] - b[1])
  
  for (const [num, count] of freq) {
    heap.push([num, count])
    if (heap.size() > k) heap.pop()
  }
  
  return heap.toArray().map(([num]) => num)
}

K Closest Points to Origin

Use a max heap of size K. As you process each point, evict the farthest if the heap exceeds K. The remaining K entries are the closest.

function kClosest(points: number[][], k: number): number[][] {
  const maxHeap = new MaxHeap<[number[][], number]>((a, b) => b[1] - a[1])
  
  for (const point of points) {
    const dist = point[0] ** 2 + point[1] ** 2
    maxHeap.push([point, dist])
    if (maxHeap.size() > k) maxHeap.pop()
  }
  
  return maxHeap.toArray().map(([point]) => point)
}

Merge K Sorted Lists

A min heap can also merge K sorted lists in O(n log k) time by always yielding the smallest current head across all K lists.

function mergeKLists(lists: ListNode[][]): number[] {
  const heap = new MinHeap<{ val: number; listIdx: number; elemIdx: number }>(
    (a, b) => a.val - b.val
  )
  
  // Seed with first element from each list
  for (let i = 0; i < lists.length; i++) {
    if (lists[i].length > 0) heap.push({ val: lists[i][0], listIdx: i, elemIdx: 0 })
  }
  
  const result: number[] = []
  while (!heap.isEmpty()) {
    const { val, listIdx, elemIdx } = heap.pop()!
    result.push(val)
    if (elemIdx + 1 < lists[listIdx].length) {
      heap.push({ val: lists[listIdx][elemIdx + 1], listIdx, elemIdx: elemIdx + 1 })
    }
  }
  return result
}

Heap Cheat Sheet

• Top K largest → min heap of size K, root is answer
• Top K smallest → max heap of size K, root is answer
• Kth largest → min heap of size K, pop once after loop
• Kth smallest → max heap of size K, pop once after loop
• K most frequent → freq map + min heap keyed by count
• Merge K sorted → min heap seeded with list heads

TypeScript does not have a built-in heap. In interviews, clarify with the interviewer whether you should implement one or assume it exists. A simple array-based binary heap implementation takes about 15 lines.

Complexity Analysis

• Time: O(n log k), inserting n elements into a heap of max size k
• Space: O(k), the heap never exceeds size k
• Compare to sorting: O(n log n) time, O(1) extra space; heap wins when k << n

Problems to Practice

• Kth Largest Element in Array (LC 215) - Classic min heap
• Top K Frequent Elements (LC 347) - Frequency + heap
• K Closest Points to Origin (LC 973) - Distance + max heap
• Find K Pairs with Smallest Sums (LC 373) - Sorted pairs
• Merge K Sorted Lists (LC 23) - Multi-way merge
• Ugly Number II (LC 264) - Multiple heaps pattern