Pattern 13: Top 'K' Elements

0. The Template (Copy-Paste Skeleton)

The counter-intuitive rule: for the k LARGEST, use a MIN-heap of size k. The top is the weakest survivor, so it is exactly the one to evict when something better arrives.

// TEMPLATE A — K LARGEST ELEMENTS (min-heap of size k)
int[] topK(int[] nums, int k) {
    PriorityQueue<Integer> heap = new PriorityQueue<>();   // MIN-heap — yes, min
    for (int x : nums) {
        heap.offer(x);
        if (heap.size() > k) heap.poll();     // evict the SMALLEST → the k largest survive
    }
    // heap now holds the k largest; heap.peek() is the k-th largest
    return heap.stream().mapToInt(Integer::intValue).toArray();
}

// TEMPLATE B — TOP K FREQUENT (count, then heap on the counts)
Map<Integer, Integer> freq = new HashMap<>();
for (int x : nums) freq.merge(x, 1, Integer::sum);

PriorityQueue<int[]> heap = new PriorityQueue<>((a, b) -> Integer.compare(a[1], b[1])); // by count ASC
for (Map.Entry<Integer, Integer> e : freq.entrySet()) {
    heap.offer(new int[]{e.getKey(), e.getValue()});
    if (heap.size() > k) heap.poll();          // drop the least frequent
}

// TEMPLATE C — K CLOSEST TO A POINT/TARGET (MAX-heap of size k, ordered by distance)
PriorityQueue<int[]> heap = new PriorityQueue<>(
        (a, b) -> Integer.compare(dist(b), dist(a)));      // MAX-heap by distance
for (int[] p : points) {
    heap.offer(p);
    if (heap.size() > k) heap.poll();          // evict the FARTHEST
}

// TEMPLATE D — BUCKET SORT: O(n) when the key is a bounded count (beats the heap)
List<Integer>[] buckets = new List[nums.length + 1];       // index = frequency
for (var e : freq.entrySet())
    buckets[e.getValue()] = buckets[e.getValue()] == null
        ? new ArrayList<>(List.of(e.getKey()))
        : appendTo(buckets[e.getValue()], e.getKey());
// walk buckets from high frequency down, collect until you have k → O(n)

The direction rule — get this wrong and everything inverts

You want	Heap type	Evict when size > k	Reason
k largest	min-heap	poll() removes the smallest	the top is the weakest survivor
k smallest	max-heap	poll() removes the largest	the top is the worst survivor
k closest	max-heap by distance	removes the farthest	same logic, distance as the key
k most frequent	min-heap by count	removes the least frequent	same logic, count as the key

Mnemonic: the heap’s top is always the element you’re most willing to throw away.

Java specifics

• new PriorityQueue<>() is a min-heap. Max-heap: Comparator.reverseOrder().
• Never (a, b) -> b - a — overflows near Integer.MAX_VALUE. Use Integer.compare(b, a).
• PriorityQueue iteration is not sorted — only poll() yields order. Don’t for-loop a heap and expect ranked output.
• new PriorityQueue<>(collection) heapifies in O(n), not O(n log n).
• heap.remove(Object) is O(n) (linear scan). Prefer lazy deletion.

Complexity — and when the heap is the wrong answer

Approach	Time	When
Sort everything	O(n log n)	k ≈ n, or you need the full order
Heap of size k	O(n log k)	the default answer; also the only one that works on a stream
Quickselect (nums[k] partition)	O(n) average, O(n²) worst	k-th element in a fixed array, no order needed
Bucket sort	O(n)	the key is a bounded integer (a frequency ≤ n) — LC 347

If the interviewer says “the data arrives as a stream / doesn’t fit in memory”, the heap is the only valid answer — Quickselect and bucket sort both need the whole array up front.

---

1. Pattern Identification & Logic

How to Identify (Interview Triggers)

• “Find the K largest / smallest” elements
• “K most frequent” or “K closest”
• “Sort partially” (only need top K, not full sort)
• “K-th” element in sorted order
• Streaming data with a size constraint

The Algorithm (Pseudocode)

Using Min-Heap of size K (for K largest):

minHeap = new PriorityQueue(size K)

for each element:
    minHeap.add(element)
    if minHeap.size() > K:
        minHeap.poll()     // remove smallest → only K largest remain

return minHeap contents

Using QuickSelect (for K-th element):

partition array around a pivot
if pivot is at position K: return pivot
if K < pivot position: recurse on left
else: recurse on right

The ‘Trick’ to Know

• For “K largest”, use a min-heap of size K (counter-intuitive!). The smallest element in the heap is the K-th largest overall. Anything smaller gets evicted.
• For “K smallest”, use a max-heap of size K.
• QuickSelect gives O(n) average but O(n^2) worst case. Heap approach is O(n log K) guaranteed.

---

2. Java Implementation (Brute Force vs. Optimal)

Example Problem: Kth Largest Element in an Array - LC 215

Brute Force: Full Sort - O(n log n)

class Solution {
    public int findKthLargest(int[] nums, int k) {
        Arrays.sort(nums);
        return nums[nums.length - k];
    }
}

Optimal: Min-Heap of Size K - O(n log k)

class Solution {
    public int findKthLargest(int[] nums, int k) {
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();

        for (int num : nums) {
            minHeap.offer(num);
            if (minHeap.size() > k) {
                minHeap.poll();
            }
        }

        return minHeap.peek();
    }
}

Example Problem: Top K Frequent Elements - LC 347

Optimal: HashMap + Min-Heap - O(n log k)

class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        Map<Integer, Integer> freq = new HashMap<>();
        for (int num : nums) {
            freq.merge(num, 1, Integer::sum);
        }

        PriorityQueue<Map.Entry<Integer, Integer>> minHeap =
            new PriorityQueue<>(Comparator.comparingInt(Map.Entry::getValue));

        for (Map.Entry<Integer, Integer> entry : freq.entrySet()) {
            minHeap.offer(entry);
            if (minHeap.size() > k) {
                minHeap.poll();
            }
        }

        return minHeap.stream().mapToInt(e -> e.getKey()).toArray();
    }
}

Java Architecture Insights

• PriorityQueue comparator: Comparator.comparingInt(Map.Entry::getValue) is cleaner than lambda for method references.
• Map.merge(key, 1, Integer::sum): Modern Java way to increment frequency. Equivalent to getOrDefault(key, 0) + 1 but more concise.
• Why min-heap for “K largest”? We want to evict the smallest of our K candidates. Min-heap’s poll() gives us the smallest in O(log k).

---

3. Mental Model & Visualization

ASCII Diagram (nums=[3,2,1,5,6,4], k=2)

Process each number with min-heap of size 2:

Add 3: heap=[3]
Add 2: heap=[2,3]
Add 1: heap=[1,2,3] → size>2, poll 1 → heap=[2,3]
Add 5: heap=[2,3,5] → size>2, poll 2 → heap=[3,5]
Add 6: heap=[3,5,6] → size>2, poll 3 → heap=[5,6]
Add 4: heap=[4,5,6] → size>2, poll 4 → heap=[5,6]

Answer: heap.peek() = 5 (2nd largest)

Senior Mental Trigger

“K largest = min-heap of size K. K smallest = max-heap of size K. Counter-intuitive but O(n log k).”

---

4. Curated Problem Lists

Commonly Asked (Bread & Butter)

#	Problem	Difficulty
LC 215	Kth Largest Element in an Array	Medium
LC 347	Top K Frequent Elements	Medium
LC 703	Kth Largest Element in a Stream	Easy
LC 973	K Closest Points to Origin	Medium
LC 692	Top K Frequent Words	Medium

FAANG ‘Aha!’ Level (Hard/Unintuitive)

#	Problem	Difficulty
LC 373	Find K Pairs with Smallest Sums	Medium
LC 355	Design Twitter	Medium
LC 767	Reorganize String	Medium
LC 659	Split Array into Consecutive Subseq	Medium
LC 378	Kth Smallest Element in Sorted Matrix	Medium

---

5. Time & Space Complexity Table

Approach	Time	Space	Notes
Full Sort	O(n log n)	O(1)	Sort entire array
Heap (size K)	O(n log k)	O(k)	Optimal when k << n
QuickSelect	O(n) avg	O(1)	O(n^2) worst case
Bucket Sort	O(n)	O(n)	When frequency range is bounded