LeetCode 703 - Kth Largest Element in a Stream

Difficulty: 🟢 Easy
Topics: Tree, Design, Binary Search Tree, Heap (Priority Queue), Binary Tree, Data Stream

Solution

Problem Understanding

The problem asks us to design a data structure that continuously tracks the kth largest element in a stream of integers.

We are given an integer k and an initial list of numbers called nums. After initialization, new numbers are added one at a time using the add method. After each insertion, we must immediately return the current kth largest value among all numbers seen so far.

The phrase "kth largest" means the element that would appear in position k if all values were sorted in descending order.

For example, if the numbers are:

[10, 8, 5, 4, 3]

then:

1st largest = 10
2nd largest = 8
3rd largest = 5

So if k = 3, the answer is 5.

An important detail is that duplicates count separately. If the stream is:

[7, 7, 7, 8]

then the sorted order is:

[8, 7, 7, 7]

and the 4th largest element is still 7.

The constraints tell us several important things:

Up to 10^4 numbers may exist initially.
Up to 10^4 calls to add may occur.
Values range from -10^4 to 10^4.

This means a solution that repeatedly sorts the entire stream after every insertion could become expensive. Since we may perform thousands of insertions, we need a structure that efficiently maintains only the information necessary to answer the query.

Several edge cases are important:

The initial array may be empty.
k may equal 1, meaning we always track the maximum element.
k may equal