Kth Largest Element in a Stream

Design a class to find the kth largest element in a stream. The class should support: KthLargest(k, nums) and add(val) which returns the kth largest element after adding val.

Example 1

Input: k=3, nums=[4,5,8,2], add(3)→4, add(5)→5, add(10)→5, add(9)→8, add(4)→8

Solution Approach

Maintain a min-heap of size k. The kth largest is always at the top of the heap.

Initialize min-heap with up to k elements from nums.
On add(val): offer val to heap; if size > k, poll the minimum.
Return heap.peek() (the kth largest).

Java

import java.util.*;

class KthLargest {
    PriorityQueue<Integer> minHeap;
    int k;

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

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

Time Complexity: add: O(log k)
Space Complexity: O(k)