CodeWithYash

Intermediate · Module 14 · Lesson 3

Top K

Keep only the most relevant k values.

15–25 min readLesson 79 of 123

Lesson 79 of 123

1d streak

Top K Elements: The Min-Heap of Size K Pattern

To find the K largest elements in an array of size $N$, sorting takes $O(N log N)$. Using a Min-Heap of size K solves it in O(N log K) time and O(K) space.

Architectural Boundary · Do Not Confuse

Concept A

Finding K Largest -> Use MIN-HEAP of Size K

Concept B

Finding K Smallest -> Use MAX-HEAP of Size K

A Min-Heap of size K keeps the smallest of the top-K elements at the root. When a new candidate arrives, if candidate > heap.peek(), we poll the root and insert the candidate. The root acts as a gatekeeper!

KthLargest.java
// Find the Kth largest element in O(n log k) time and O(k) space
public int findKthLargest(int[] nums, int k) {
    PriorityQueue<Integer> minHeap = new PriorityQueue<>(k); // Default in Java is Min-Heap

    for (int num : nums) {
        minHeap.offer(num);
        if (minHeap.size() > k) {
            minHeap.poll(); // Evict the smallest candidate
        }
    }
    // Root of minHeap is the Kth largest element!
    return minHeap.peek();
}

Cost Model

Complexity & Trade-offs

Push / pop
O(log n)
O(n)
Reading the root is O(1); heap construction is O(n).

When to use it

  • Top-k, streaming medians, scheduling, and best-first frontiers.
  • Repeated access to an extreme without fully sorting.
  • Merging sorted sources.

Common mistakes

  • Choosing the wrong heap direction for a bounded top-k set.
  • Assuming heap iteration is globally sorted.
  • Claiming bottom-up heap construction is O(n log n).

Practice prompts

  • Reproduce the worked Top K example without looking at the trace.
  • Change one input condition and explain whether the Top K invariant still holds.
  • Implement the approach, derive its cost, and compare it with a straightforward baseline.

Mastery check

Can you derive it instead of memorizing it?

State the invariant before looking at code.
Explain why every transition is safe.
Construct a worst-case input.
Name one alternative and its trade-off.