DSA problem
Kth Largest Element in a Stream
Design a class to find the k-th largest element in a stream of integers. Note that it is the k-th largest element in sorted order, not the k-th distinct element. You must implement a KthLargest class whose constructor accepts an integer k and an initial integer array nums, and an add(val) method that appends val to the stream and returns the element representing the k-th largest element in the stream so far.
The naive way to answer each query is to sort the buffered numbers in descending order and read off index k - 1. That costs O(n log n) every time a new value arrives, which is wasteful because each add call inserts only one element — almost all of the previous structure carries over.
The right structure for this problem is a min-heap of size k. Because the heap holds exactly the top k largest values seen so far, the smallest of those — the heap's root — is precisely the k-th largest in the stream. On every insertion, push the new value, and if the heap now exceeds k elements, pop the smallest. Whatever sits at the root afterwards is the answer.
This design uses O(k) extra space, performs the constructor in O(n log k) time, and answers every add query in O(log k) time. It scales gracefully even as the stream grows to millions of elements, because per-call cost depends only on k, not on the stream length.
Examples
["KthLargest","add","add","add","add","add"]
[[3,[4,5,8,2]],[3],[5],[10],[9],[4]][null,4,5,5,8,8]["KthLargest","add","add","add"]
[[1,[]],[-3],[-2],[-4]][null,-3,-2,-2]["KthLargest","add","add"]
[[2,[0]],[1],[2]][null,0,1]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.
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.