Kth Largest Element in a Stream
Easy · Heap & Counting · Tree · Design · Binary Search Tree · Heap (Priority Queue) · Data Stream
Problem
Design a class that reports the k-th largest value in a stream of numbers, like a leaderboard that always shows the score needed to make the top k.
- KthLargest(k, nums) creates it with k and the values nums seen so far.
- add(val) adds val to the stream and returns the k-th largest value seen so far. Duplicates count: this is the k-th value in sorted order, not the k-th distinct one.
Whenever add returns, at least k values have been seen.
Tests replay a call sequence: the first entry names the class and its constructor arguments, each later entry is a method with its arguments, and the constructor reports None.
Examples
Input: KthLargest(2, [5,1,7]), add(3), add(8), add(6), add(2) Output: 5, then 7, then 7, then 7
The top two are 7, 5 after adding 3; 8, 7 after adding 8; 6 and 2 do not displace 7.
Input: KthLargest(3, [4,4]), add(-1), add(4), add(10) Output: -1, then 4, then 4
The third largest of 4, 4, -1 is -1; after another 4 the top three are 4, 4, 4; after 10 they are 10, 4, 4.
Constraints
- 1 <= k <= 10^4
- 0 <= len(nums) <= 10^4
- -10^4 <= nums[i], val <= 10^4
- add is called at most 10^4 times
- at least k values have been seen whenever add returns
Approaches
- Baseline: keep every value sorted — time O(n) per add, space O(n)
Follow-up
Every value that falls out of the heap is smaller than k others, so it can never return to the top k: that is why throwing it away is safe, and why memory stays O(k) however long the stream runs. If values could also be removed from the stream, that argument breaks and you would need a balanced tree or two heaps with lazy deletion. The use cases below keep a running total of the top k, and ignore duplicates.
Related problems
Start free on Cariara · Coding problems · System design studio
