Top K Elements Pattern | Engineering Interview Kit

Concept

Any time an interview problem contains the words “Top K”, “Largest K”, “Smallest K”, or “K Most Frequent”, your brain should immediately scream “USE A HEAP!”.

Problem: Given an unsorted array, return the K largest elements.

Naive Approach: Sort the array descending ( $O(N \log N)$ ) and slice the first K elements.
Optimal Approach: Use a Heap to solve it in $O(N \log K)$ .

The “K-Sized Min-Heap” Trick

To find the K Largest elements, you actually use a Min-Heap, not a Max-Heap!
Why? Because we want to restrict the size of the heap to exactly K to save memory and time.

Mental Model:
We want the Top 3 Largest numbers from [8, 2, 9, 1, 10, 4].
We use a Min-Heap capped at size 3.

Insert 8. [8]
Insert 2. [2, 8] (2 bubbles to top)
Insert 9. [2, 8, 9]
Insert 1. The heap size is 4! That’s too big! We must instantly .pop() the top item to bring it back to size 3. Because it’s a Min-Heap, it pops the 1 (the absolute smallest, most useless number). The heap remains [2, 8, 9].
Insert 10. [2, 8, 9, 10]. Size is 4. Pop the minimum (2). Heap is [8, 9, 10].
Insert 4. [4, 8, 9, 10]. Size is 4. Pop the minimum (4). Heap is [8, 9, 10].

By the end of the array, the Min-Heap acts as an exclusive VIP club. The smallest numbers constantly get kicked out the front door. The only numbers left standing inside the club are guaranteed to be the 3 absolute largest numbers!

Implementation

// Assuming a MinPriorityQueue class exists
function findTopKLargest(nums: number[], k: number): number[] {
    const minHeap = new MinPriorityQueue();

    for (let num of nums) {
        minHeap.enqueue(num);
        
        // The VIP Club bouncer: Kick out the smallest number!
        if (minHeap.size() > k) {
            minHeap.dequeue(); 
        }
    }

    // The remaining K items are the largest
    const result: number[] = [];
    while (!minHeap.isEmpty()) {
        result.push(minHeap.dequeue().element);
    }
    
    return result; // Returns the Top K in ascending order
}

Why is it $O(N \log K)$ ?

We iterate through all $N$ elements in the array.
For each element, we insert it into the Heap. Because we strictly enforce minHeap.size() > k, the Heap physically never grows larger than $K$ items.
Therefore, the bubble up/down operations take $O(\log K)$ time, rather than $O(\log N)$ .
Total time: $N \times \log K = O(N \log K)$ .

If you have 10 Million users ( $N$ ), and you want the Top 10 High Scores ( $K$ ), $\log(10)$ is essentially $1$ . The algorithm runs in pure $O(N)$ time with microscopic $O(1)$ memory usage!

K Closest Points to Origin

Problem: Given an array of coordinates [[1,3], [-2,2], [5,-1]], find the K closest points to the origin (0,0). (LeetCode 973).

The “Top K Elements” pattern applies to anything that can be scored!
To find the K Closest (smallest distance), we flip the pattern: we use a Max-Heap.

Calculate the distance for a point: $x^2 + y^2$ .
Push { point, distance } into the Max-Heap.
If the Heap exceeds size K, .dequeue(). Because it’s a Max-Heap, it kicks out the point with the largest distance (the farthest, most useless point).
You are left with the K closest points.

Interview Questions