Coding Interview Patterns

The Top-K Heap Pattern

Keeping a heap of size k instead of sorting the entire input turns "find the k largest/smallest" into O(n log k) — a real win whenever k is much smaller than n, and the only option when the data is a stream.

For the k largest elements, keep a min-heap of size k — counterintuitive, but it lets you discard the current smallest of the k candidates in O(log k) whenever a bigger element arrives
For the k smallest, invert it: a max-heap of size k
Java's PriorityQueue is the natural container — offer to add, poll the root to evict when size exceeds k
Works on streaming data you can't fully hold in memory or sort — the heap only ever holds k elements
"Merge k sorted lists" is the same pattern in disguise: a heap of k pointers, always popping the smallest and advancing that pointer

K largest elements with a min-heap

static int[] kLargest(int[] nums, int k) {
    PriorityQueue<Integer> minHeap = new PriorityQueue<>();   // natural order = min-heap
    for (int n : nums) {
        minHeap.offer(n);
        if (minHeap.size() > k) minHeap.poll();               // evict the current smallest of the k
    }
    int[] result = new int[k];
    for (int i = k - 1; i >= 0; i--) result[i] = minHeap.poll();
    return result;
}

Top-k: heap vs alternatives
Approach	Time	Space	Works on a stream
Sort everything	O(n log n)	O(n) or O(1) in-place	no
Size-k heap	O(n log k)	O(k)	yes
Quickselect (Order Statistics Selection)	O(n) expected	O(1) extra	no — needs full random access