Kth Largest Element in a Stream

Kth Largest Element in a Stream

1. What is this problem about?

The Kth Largest Element in a Stream interview question asks you to design a class that can handle a continuous flow of numbers. You need to provide an add(val) method that inserts a new number and returns the current $k^{th}$ largest element in the entire stream.

2. Why is this asked in interviews?

This is a flagship question for Design interview patterns and Priority Queues. Companies like Meta and Atlassian ask this to see if you can avoid sorting the entire list every time a new number is added ($O(N \log N)$). The goal is to achieve $O(\log K)$ time per addition by only keeping the "interesting" part of the data.

3. Algorithmic pattern used

This problem is the quintessential use case for a Min-Heap.

1. The Heap Strategy: Maintain a Min-Heap containing only the top $k$ largest elements seen so far.
2. Logic:
   • The smallest element in this top-$k$ set is the $k^{th}$ largest overall.
   • Because it's a Min-Heap, this $k^{th}$ largest element is always at the top.
3. Addition:
   • Push the new value into the heap.
   • If the heap size exceeds $k$, pop the smallest element (it's no longer in the top $k$).
4. Efficiency: add is $O(\log K)$, and show is $O(1)$.

4. Example explanation

$k = 3$, initial stream [4, 5, 8, 2]

1. Heap (size 3): [4, 5, 8]. (2 was popped). $k^{th}$ largest is 4.
2. add(3): Heap [3, 4, 5, 8] -> pop 3 -> [4, 5, 8]. Result: 4.
3. add(5): Heap [4, 5, 5, 8] -> pop 4 -> [5, 5, 8]. Result: 5.
4. add(10): Heap [5, 5, 8, 10] -> pop 5 -> [5, 8, 10]. Result: 5.

5. Common mistakes candidates make

• Max-Heap: Using a Max-Heap to store all elements. To get the $k^{th}$ largest, you'd have to pop $k$ times and push back, making it $O(K \log N)$.
• Sorting: Re-sorting the list on every add, which is $O(N \log N)$.
• Heap size: Not keeping the heap fixed at size $k$, which wastes memory and slows down additions.

6. Interview preparation tip

Remember the rule: "To find the $k^{th}$ largest, use a Min-Heap of size $k$. To find the $k^{th}$ smallest, use a Max-Heap of size $k$." This is a fundamental Heap interview pattern.