Top K Elements

1. 1.Kth Largest Element in an Array
   Min Heap size K in O(N log K) time or Quickselect in O(N)medium
2. 2.Top K Frequent Elements
   HashMap frequency + Min Heap size K or Bucket Sort in O(N)medium
3. 3.K Closest Points to Origin
   Max Heap size K storing (dist = x^2 + y^2, point)medium
4. 4.Kth Largest Element in a Stream
   Maintain Min Heap of size Keasy
5. 5.Find K Pairs with Smallest Sums
   Min Heap storing (u + v, i, j) index pairsmedium
6. 6.Kth Smallest Element in a Sorted Matrix
   Min Heap row candidates or Binary Search on rangemedium
7. 7.Find K Closest Elements
   Binary search window + 2 pointers or Max Heap distancemedium
8. 8.Top K Frequent Words
   Min Heap size K with custom tie-breaker alphabetical comparatormedium
9. 9.Merge K Sorted Lists
   Min Heap storing candidate node pointers from each listhard
10. 10.Kth Smallest Number in Multiplication Table
    Binary Search on answer range 1..m*nhard
11. 11.Kth Smallest Prime Fraction
    Min Heap storing (a/b, i, j) fraction pairsmedium
12. 12.Sort Characters By Frequency
    Frequency HashMap + Bucket Sort or Max Heapmedium
13. 13.Reorganize String
    Max Heap of character counts + previous character holdmedium
14. 14.Find Median from Data Stream
    Two Heaps: Max Heap (lower half) + Min Heap (upper half)hard
15. 15.K Closest Points to Origin
    Max Heap of size K keeping smallest distancesmedium

1. 16.Kth Smallest Element in a BST
   Inorder traversal with counter Kmedium
2. 17.Ugly Number II
   Min Heap generating numbers multiplied by 2, 3, 5 + HashSetmedium
3. 18.Smallest Range Covering Elements from K Lists
   Min Heap storing current elements across K listshard
4. 19.Maximum Performance of a Team
   Sort by efficiency + Min Heap of speed sum for top K engineershard
5. 20.Total Cost to Hire K Workers
   Two Min Heaps for first & last candidate windowshard
6. 21.IPO
   Sort projects by capital + Max Heap for available profitshard
7. 22.Minimum Cost to Connect Sticks
   Min Heap combining two smallest sticks repeatedly (Greedy)medium
8. 23.K Weakest Rows in a Matrix
   Max Heap size K storing (soldier_count, row_index)easy
9. 24.Find Subsequence of Length K With Largest Sum
   Min Heap size K storing (value, index) + sort by indexeasy

How to Think

1. Need K largest elements?Min Heap of size K (evict root when size > K)
2. Need K smallest elements?Max Heap of size K (evict root when size > K)
3. Need Top K by frequency?Hash Map + Min Heap size K or Bucket Sort
4. Need closest K items?Distance (x² + y²) + Max Heap of size K
5. K is much smaller than N?Don't sort all N items! Use Heap O(N log K)

// Maintain Min Heap of size K for Top K Largest elements
h := &IntHeap{}
heap.Init(h)

for _, val := range nums {
    heap.Push(h, val)

    // When size exceeds K, evict the weakest candidate at root!
    if h.Len() > k {
        heap.Pop(h)
    }
}

// h now contains the Top K largest elements in O(N log K) time!
// Root h[0] is the K-th largest element.

5 Core Top K Sub-Patterns

Bucket Sort for Top K Frequency (O(N) Time Optimization)

// 1. Build frequency map
counts := map[int]int{}
for _, num := range nums { counts[num]++ }

// 2. Build buckets array where index = frequency count
buckets := make([][]int, len(nums)+1)
for num, count := range counts {
    buckets[count] = append(buckets[count], num)
}

// 3. Scan buckets from right to left (highest frequency to lowest)
result := []int{}
for i := len(buckets)-1; i >= 0 && len(result) < k; i-- {
    if len(buckets[i]) > 0 {
        result = append(result, buckets[i]...)
    }
}

Top K Largest   → Min Heap size K (evict weakest root)
Top K Smallest  → Max Heap size K (evict largest root)
Top K Frequent  → HashMap + Min Heap size K OR Bucket Sort O(N)
Distance check  → Use x² + y² (No square root needed!)

Common Interview Mistakes

Interview Rules

1. 1. K largest elements? → Min Heap size K (O(N log K) time, O(K) space)
2. 2. K smallest elements? → Max Heap size K
3. 3. Kth largest item only? → Min Heap top OR Quickselect (O(N) average)
4. 4. Top K frequent? → Frequency Map + Heap OR Bucket Sort (O(N) time)
5. 5. K closest items? → Distance x^2 + y^2 + Max Heap size K
6. 6. Weakest candidate rule → Evict root whenever heap size exceeds K
7. 7. Sort final output? → Heap is not sorted; sort the K popped items in O(K log K) if required
8. 8. K close to N? → If $K \approx N$, full sorting in O(N log N) is simpler and reasonable

Top K Largest   → Min Heap K
Top K Smallest  → Max Heap K
Top K Frequent  → Map + Heap / Bucket Sort
K Closest       → Distance + Heap
Only Kth item   → Quickselect
Heap too big    → Remove weakest
N huge, K small → Don't sort everything
Heap approach   → O(n log k)

💡 Golden Rule: "Keep only the K best candidates, and always make the weakest one easy to remove."