Skip to content
AI360Xpert
Back to Heap / Priority Queue
Easy

Kth Largest Element in a Stream

Design a class to find the `k`th largest element in a stream. Note that it is the `k`th largest element in the sorted order, not the `k`th distinct element. Implement `KthLargest` class: `KthLargest(int k, int[] nums)` Initializes the object with the integer `k` and the stream of integers `nums`. `int add(int val)` Appends the integer `val` to the stream and returns the element representing the `k`th largest element in the stream.

Examples

Input:["KthLargest", "add", "add", "add", "add", "add"] [[3, [4, 5, 8, 2]], [3], [5], [10], [9], [4]]
Output:[null, 4, 5, 5, 8, 8]
KthLargest kthLargest = new KthLargest(3, [4, 5, 8, 2]); kthLargest.add(3); // return 4 kthLargest.add(5); // return 5 kthLargest.add(10); // return 5 kthLargest.add(9); // return 8 kthLargest.add(4); // return 8

Constraints

  • 1 <= k <= 10^4
  • 0 <= nums.length <= 10^4
  • -10^4 <= nums[i] <= 10^4
  • -10^4 <= val <= 10^4
  • At most 10^4 calls will be made to add.
  • It is guaranteed that there will be at least k elements in the array when you search for the kth element.

Min Heap

Approach

Use a Min Heap to store the `k` largest elements seen so far. Initialize the heap with the first `k` elements of `nums`. For every new element added (including the remaining elements in initialization), push it to the heap. If the heap size exceeds `k`, pop the smallest element (which is at the root of the Min Heap). The `k`th largest element will always be the smallest element in our heap of size `k`, which is at the root/top of the Min Heap.

Complexity Analysis

Time Complexity
O(N log K) init, O(log K) add
Space Complexity
O(K)

N is the initial number of elements. The space complexity is O(K) because we only keep K elements in the heap.

Solution.java
class KthLargest {    private PriorityQueue<Integer> minHeap;    private int k;
    public KthLargest(int k, int[] nums) {        this.k = k;        this.minHeap = new PriorityQueue<>();                for (int num : nums) {            add(num);        }    }        public int add(int val) {        minHeap.offer(val);        if (minHeap.size() > k) {            minHeap.poll();        }        return minHeap.peek();    }}