easyHeap / Priority Queue

Kth Largest Element in a Stream

Maintain the kth largest value as numbers arrive. Count duplicates as separate entries.

LeetCode ↗

Work through the cases

3 examples

Input notation

k on line 1, initial values on line 2, values to add on line 3. The initial list has at least k values.

Expected result

The kth largest value after each addition, separated by spaces.

Case 1

Input

2
4 7 1
5 9

Expected output

5 7

Case 2

Input

1
2
1 3

Expected output

2 3

Case 3

Input

2
-3 -2
-1 -1

Expected output

-2 -1

These notes use simplified input/output notation. The linked platform defines the method signature and judge format.

FROM IDEA TO IMPLEMENTATION

Understand the approach.

Compare the documented approaches below. Brute force, better, and optimal versions appear where available; a direct exercise may need only one approach.

We insert into a stream and must report the k-th largest after each add. Sorting or scanning the whole history on every query is too heavy when both n and the query count reach 10^4. Only the current top k values matter; anything smaller can never be the answer. In a size-k min-heap the top is the smallest of those k, i.e. the k-th largest overall. Push each new value and pop if the heap grows past k. Seeding from nums uses the same add. Each update is O(log k).

We maintain a priority queue (min heap) minQ.

Initially, we add the elements of the array nums to minQ one by one, ensuring that the size of minQ does not exceed k. The time complexity is O(n × log k).

Each time a new element is added, if the size of minQ exceeds k, we pop the top element of the heap to ensure that the size of minQ is k. The time complexity is O(log k).

In this way, the elements in minQ are the largest k elements in the array nums, and the top element of the heap is the k^{th} largest element.

The space complexity is O(k).

class KthLargest {
    private PriorityQueue<Integer> minQ;
    private int k;

    public KthLargest(int k, int[] nums) {
        this.k = k;
        minQ = new PriorityQueue<>(k);
        for (int x : nums) {
            add(x);
        }
    }

    public int add(int val) {
        minQ.offer(val);
        if (minQ.size() > k) {
            minQ.poll();
        }
        return minQ.peek();
    }
}

/**
 * Your KthLargest object will be instantiated and called as such:
 * KthLargest obj = new KthLargest(k, nums);
 * int param_1 = obj.add(val);
 */

Reference code. Platform solutions may use supplied node types, imports, or collection libraries; foundational examples are complete programs.

Solutions adapted from Doocs / LeetCode contributors, licensed under CC BY-SA 4.0. Formatting changed; TypeScript versions converted to JavaScript. Supplemental implementations and approach notes added. Adapted solution material is available under the same license.