286. Kth Largest Element in a Stream

Keep a min-heap holding only the k largest elements seen so far. Its smallest element (the heap root) is exactly the kth largest overall.

Only the top k matter

To know the kth largest, you never need more than the k largest values. Maintain a min-heap capped at size k: after each insert, if the heap exceeds k, pop the smallest. The root is then the kth largest.

KthLargest(k, nums): push all nums, trimming to size k
add(val): push val; if size > k: pop smallest; return heap top

Worked example

k=3, nums=[4,5,8,2] → heap keeps [4,5,8], root 4. add(3)→ still [4,5,8], root 4. add(5)→ [5,5,8], root 5. add(10)→ [5,8,10], root 5. add(9)→ [8,9,10], root 8.

Complexity

• Time: O(log k) per add.
• Space: O(k).

import java.util.PriorityQueue;

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

    public KthLargest(int k, int[] nums) {
        this.k = k;
        heap = new PriorityQueue<>();  // min-heap
        for (int n : nums) {
            heap.offer(n);
            if (heap.size() > k) heap.poll();
        }
    }

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