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 entire array. Time: O(n log k) vs O(n log n) for full sort.

Kth Largest Element

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

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

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)
}

Heap Cheat Sheet

• Top K largest → use min heap of size K
• Top K smallest → use max heap of size K
• Kth largest → min heap, return root
• Kth smallest → max heap, return root

TypeScript doesn't have a built-in heap. Use a library or implement your own.