Kth Largest Element in a Stream
Kth Largest Element in a Stream is a easy heaps problem solved with the top k / kth largest / smallest pattern.
The best approach, optimal (min-heap of size k), runs in O(log k) per add time and O(k) space.
Below are 2 approaches in Java, Python, C++ and JavaScript, from sorted list up.
Problem
Design a class that receives a stream of numbers and, after each new number, returns the k-th largest number seen so far.
Examples
Example 1
- Input
KthLargest(3, [4, 5, 8, 2]); add(3); add(5); add(10); add(9); add(4)- Output
4, 5, 5, 8, 8
Constraints
1 <= k <= 10^4; up to10^4calls to add.- There are at least k elements whenever you query.
Solve it here
Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
Run checks the testcases above (1 examples, or your own). Submit also runs 9 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.
Animated walkthrough
A narrated, step-by-step animation that builds the solution from the idea up. Press play, or step through it at your own pace.
Concepts first, then the problem and every approach, step by step.
Space to play or pause · ← → to jump a step · click or drag the bar to seek
Solutions
Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.
| Approach | Time | Space |
|---|---|---|
| Sorted list | O(n) per add | O(n) |
| Optimal (min-heap of size k) | O(log k) per add | O(k) |
1Sorted list
O(n) per addInserting into an array list shifts elements.O(n)Keep all values in a sorted list (binary search insert) and read index size - k.
- Insert at bisect position; return list[size - k].
class KthLargest {
private final List<Integer> vals = new ArrayList<>();
private final int k;
public KthLargest(int k, int[] nums) {
this.k = k;
for (int x : nums) insert(x);
}
public int add(int val) {
insert(val);
return vals.get(vals.size() - k);
}
private void insert(int x) {
int i = Collections.binarySearch(vals, x);
vals.add(i < 0 ? -i - 1 : i, x);
}
}class KthLargest:
def __init__(self, k: int, nums: List[int]):
self.vals: List[int] = []
self.k = k
for x in nums:
self.insert(x)
def add(self, val: int) -> int:
self.insert(val)
return self.vals[len(self.vals) - self.k]
def insert(self, x: int) -> None:
i = bisect.bisect_left(self.vals, x)
self.vals.insert(i, x)class KthLargest {
vector<int> vals;
int k;
public:
KthLargest(int k, vector<int> nums) {
this->k = k;
for (int x : nums) insert(x);
}
int add(int val) {
insert(val);
return vals[vals.size() - k];
}
private:
void insert(int x) {
auto it = lower_bound(vals.begin(), vals.end(), x);
vals.insert(it, x);
}
};class KthLargest {
constructor(k, nums) {
this.vals = [];
this.k = k;
for (const x of nums) this.insert(x);
}
add(val) {
this.insert(val);
return this.vals[this.vals.length - this.k];
}
insert(x) {
let lo = 0, hi = this.vals.length;
while (lo < hi) {
const mid = (lo + hi) >> 1;
if (this.vals[mid] < x) lo = mid + 1; else hi = mid;
}
this.vals.splice(lo, 0, x);
}
}2Optimal (min-heap of size k)
O(log k) per addO(k)Keep a min-heap of the k largest values. On add, push; if the heap grows past k, pop the smallest. The top is the k-th largest.
- Constructor: add each initial value.
- add: offer; if size > k, poll; return peek.
class KthLargest {
private final PriorityQueue<Integer> heap = new PriorityQueue<>();
private final int k;
public KthLargest(int k, int[] nums) {
this.k = k;
for (int x : nums) add(x);
}
public int add(int val) {
heap.offer(val);
if (heap.size() > k) heap.poll();
return heap.peek();
}
}class KthLargest:
def __init__(self, k: int, nums: List[int]):
self.heap: List[int] = []
self.k = k
for x in nums:
self.add(x)
def add(self, val: int) -> int:
heapq.heappush(self.heap, val)
if len(self.heap) > self.k:
heapq.heappop(self.heap)
return self.heap[0]class KthLargest {
priority_queue<int, vector<int>, greater<int>> heap;
int k;
public:
KthLargest(int k, vector<int> nums) {
this->k = k;
for (int x : nums) add(x);
}
int add(int val) {
heap.push(val);
if ((int)heap.size() > k) heap.pop();
return heap.top();
}
};class MinHeap {
constructor(cmp = (a, b) => a - b) { this.a = []; this.cmp = cmp; }
size() { return this.a.length; }
isEmpty() { return this.a.length === 0; }
peek() { return this.a[0]; }
push(x) {
const a = this.a;
a.push(x);
let i = a.length - 1;
while (i > 0) {
const p = (i - 1) >> 1;
if (this.cmp(a[i], a[p]) >= 0) break;
[a[i], a[p]] = [a[p], a[i]];
i = p;
}
}
pop() {
const a = this.a, top = a[0], last = a.pop();
if (a.length > 0) {
a[0] = last;
let i = 0;
while (true) {
const l = 2 * i + 1, r = l + 1;
let m = i;
if (l < a.length && this.cmp(a[l], a[m]) < 0) m = l;
if (r < a.length && this.cmp(a[r], a[m]) < 0) m = r;
if (m === i) break;
[a[i], a[m]] = [a[m], a[i]];
i = m;
}
}
return top;
}
}
class KthLargest {
constructor(k, nums) {
this.heap = new MinHeap();
this.k = k;
for (const x of nums) this.add(x);
}
add(val) {
this.heap.push(val);
if (this.heap.size() > this.k) this.heap.pop();
return this.heap.peek();
}
}Edge cases to test
- The initial array has fewer than k elements
- A new value smaller than the current k-th largest
Hints
Hint 1
A min-heap of size k keeps exactly the k largest values, with the answer on top.
FAQ
What is the best time complexity for Kth Largest Element in a Stream?
Optimal (min-heap of size k) runs in O(log k) per add time and O(k) extra space.
Which pattern does Kth Largest Element in a Stream use?
It is a heaps problem that uses the top k / kth largest / smallest pattern. Other problems with the same pattern: Kth Largest Element in an Array, Top K Frequent Words, K Closest Points to Origin.
Is there a brute force solution for Kth Largest Element in a Stream?
Yes. Sorted list takes O(n) per add time and O(n) space. Keep all values in a sorted list (binary search insert) and read index size - k.
Which edge cases should I test for Kth Largest Element in a Stream?
The initial array has fewer than k elements; A new value smaller than the current k-th largest.