.png)
Kth Largest Element in a Stream
Problem Statement
You are given an integer k and a stream of integers.
After inserting each element from the stream, you need to report the kth largest element seen so far.
If fewer than k elements have been seen, return -1.
Example
Input
k = 3
stream = [4, 5, 8, 2]
Output
[-1, -1, 4, 4]
Explanation
| Stream so far | Sorted | 3rd Largest |
|---|---|---|
| [4] | [4] | -1 |
| [4,5] | [5,4] | -1 |
| [4,5,8] | [8,5,4] | 4 |
| [4,5,8,2] | [8,5,4,2] | 4 |
Why This Problem Is Important
- Tests heap data structure
- Classic streaming problem
- Asked in Amazon, Google, Microsoft
- Foundation for real-time ranking systems
Approaches Overview
| Approach | Technique | Time (per insert) | Space |
|---|---|---|---|
| Brute Force | Sort every time | O(n log n) | O(n) |
| Better | Max Heap | O(log n) | O(n) |
| Optimal | Min Heap of size k | O(log k) | O(k) |
Approach 1- Brute Force Approach
Idea
- Insert element into array
- Sort array in descending order
- Pick kth element if exists
Time and Space Complexity
- Time: O(n log n) per insertion
- Space: O(n)
C++ Implementation
#include
using namespace std;
class KthLargest {
int k;
vector arr;
public:
KthLargest(int k) : k(k) {}
int add(int val){
arr.push_back(val);
sort(arr.begin(), arr.end(), greater());
if(arr.size() < k) return -1;
return arr[k-1];
}
};
int main(){
KthLargest obj(3);
cout << obj.add(4) << endl;
cout << obj.add(5) << endl;
cout << obj.add(8) << endl;
cout << obj.add(2) << endl;
cout << obj.add(10) << endl;
cout << obj.add(9) << endl;
}
Java Implementation
import java.util.*;
class KthLargest {
int k;
List arr = new ArrayList<>();
KthLargest(int k){
this.k = k;
}
int add(int val){
arr.add(val);
arr.sort(Collections.reverseOrder());
if(arr.size() < k) return -1;
return arr.get(k-1);
}
public static void main(String[] args){
KthLargest obj = new KthLargest(3);
System.out.println(obj.add(4));
System.out.println(obj.add(5));
System.out.println(obj.add(8));
System.out.println(obj.add(2));
System.out.println(obj.add(10));
System.out.println(obj.add(9));
}
}
JavaScript Implementation
class KthLargest {
constructor(k){
this.k = k;
this.arr = [];
}
add(val){
this.arr.push(val);
this.arr.sort((a,b)=>b-a);
if(this.arr.length < this.k) return -1;
return this.arr[this.k-1];
}
}
let obj = new KthLargest(3);
console.log(obj.add(4));
console.log(obj.add(5));
console.log(obj.add(8));
console.log(obj.add(2));
console.log(obj.add(10));
console.log(obj.add(9));
C# Implementation
using System;
using System.Collections.Generic;
class KthLargest {
int k;
List arr = new List();
public KthLargest(int k){
this.k = k;
}
public int Add(int val){
arr.Add(val);
arr.Sort((a,b)=>b.CompareTo(a));
if(arr.Count < k) return -1;
return arr[k-1];
}
}
class Program {
static void Main(){
KthLargest obj = new KthLargest(3);
Console.WriteLine(obj.Add(4));
Console.WriteLine(obj.Add(5));
Console.WriteLine(obj.Add(8));
Console.WriteLine(obj.Add(2));
Console.WriteLine(obj.Add(10));
Console.WriteLine(obj.Add(9));
}
}
Output
-1
-1
4
4
5
8
Approach 2- Better Approach (Max Heap)
Idea
- Store all elements in a max heap
- To get kth largest:
- Remove top element k times
- The last removed element is the answer
- Push removed elements back into heap
This approach is not optimal but helps understand heap mechanics.
Time and Space Complexity
- Time per insertion: O(k log n)
- Space: O(n)
Python
import heapq
class KthLargest:
def __init__(self, k):
self.k = k
self.heap = []
def add(self, val):
heapq.heappush(self.heap, -val)
if len(self.heap) < self.k:
return -1
removed = []
for _ in range(self.k):
removed.append(heapq.heappop(self.heap))
ans = -removed[-1]
for x in removed:
heapq.heappush(self.heap, x)
return ans
# Driver Code
obj = KthLargest(3)
print(obj.add(4))
print(obj.add(5))
print(obj.add(8))
print(obj.add(2))
print(obj.add(10))
C++
#include
#include
#include
using namespace std;
class KthLargest {
int k;
priority_queue pq; // max heap
public:
KthLargest(int k) {
this->k = k;
}
int add(int val) {
pq.push(val);
if (pq.size() < k)
return -1;
vector temp;
for (int i = 0; i < k; i++) {
temp.push_back(pq.top());
pq.pop();
}
int ans = temp.back();
for (int x : temp)
pq.push(x);
return ans;
}
};
int main() {
KthLargest obj(3);
cout << obj.add(4) << endl;
cout << obj.add(5) << endl;
cout << obj.add(8) << endl;
cout << obj.add(2) << endl;
cout << obj.add(10) << endl;
return 0;
}
Java
import java.util.*;
class KthLargest {
int k;
PriorityQueue pq;
KthLargest(int k) {
this.k = k;
pq = new PriorityQueue<>(Collections.reverseOrder()); // max heap
}
int add(int val) {
pq.add(val);
if (pq.size() < k)
return -1;
List temp = new ArrayList<>();
for (int i = 0; i < k; i++)
temp.add(pq.poll());
int ans = temp.get(k - 1);
for (int x : temp)
pq.add(x);
return ans;
}
}
public class Main {
public static void main(String[] args) {
KthLargest obj = new KthLargest(3);
System.out.println(obj.add(4));
System.out.println(obj.add(5));
System.out.println(obj.add(8));
System.out.println(obj.add(2));
System.out.println(obj.add(10));
}
}
JavaScript
class MaxHeap {
constructor() {
this.data = [];
}
push(val) {
this.data.push(val);
this.data.sort((a, b) => b - a);
}
pop() {
return this.data.shift();
}
size() {
return this.data.length;
}
}
class KthLargest {
constructor(k) {
this.k = k;
this.heap = new MaxHeap();
}
add(val) {
this.heap.push(val);
if (this.heap.size() < this.k)
return -1;
let temp = [];
for (let i = 0; i < this.k; i++)
temp.push(this.heap.pop());
let ans = temp[this.k - 1];
for (let x of temp)
this.heap.push(x);
return ans;
}
}
// Driver
let obj = new KthLargest(3);
console.log(obj.add(4));
console.log(obj.add(5));
console.log(obj.add(8));
console.log(obj.add(2));
console.log(obj.add(10));
C#
using System;
using System.Collections.Generic;
class KthLargest {
int k;
PriorityQueue pq;
public KthLargest(int k) {
this.k = k;
pq = new PriorityQueue();
}
public int Add(int val) {
pq.Enqueue(val, -val); // max heap
if (pq.Count < k)
return -1;
List temp = new List();
for (int i = 0; i < k; i++)
temp.Add(pq.Dequeue());
int ans = temp[k - 1];
foreach (int x in temp)
pq.Enqueue(x, -x);
return ans;
}
}
class Program {
static void Main() {
KthLargest obj = new KthLargest(3);
Console.WriteLine(obj.Add(4));
Console.WriteLine(obj.Add(5));
Console.WriteLine(obj.Add(8));
Console.WriteLine(obj.Add(2));
Console.WriteLine(obj.Add(10));
}
}
Output
[-1, -1, 4, 4, 5]Approach 3 - Optimal Approach (Min Heap of Size k)
Idea
- Maintain a min heap of size k
- Heap contains the k largest elements seen so far
- Top of heap = kth largest element
Time and Space Complexity
- Time: O(log k) per insertion
- Space: O(k)
Python
import heapq
class KthLargest:
def __init__(self, k):
self.k = k
self.heap = []
def add(self, val):
heapq.heappush(self.heap, val)
if len(self.heap) > self.k:
heapq.heappop(self.heap)
if len(self.heap) < self.k:
return -1
return self.heap[0]
# Driver Code
kth = KthLargest(3)
print(kth.add(4)) # -1
print(kth.add(5)) # -1
print(kth.add(8)) # 4
print(kth.add(2)) # 4
print(kth.add(10)) # 5
C++
#include
#include
using namespace std;
class KthLargest {
int k;
priority_queue, greater> pq;
public:
KthLargest(int k) {
this->k = k;
}
int add(int val) {
pq.push(val);
if (pq.size() > k)
pq.pop();
if (pq.size() < k)
return -1;
return pq.top();
}
};
int main() {
KthLargest obj(3);
cout << obj.add(4) << endl;
cout << obj.add(5) << endl;
cout << obj.add(8) << endl;
cout << obj.add(2) << endl;
cout << obj.add(10) << endl;
return 0;
}
Java
import java.util.*;
class KthLargest {
int k;
PriorityQueue pq;
KthLargest(int k) {
this.k = k;
pq = new PriorityQueue<>();
}
int add(int val) {
pq.add(val);
if (pq.size() > k)
pq.poll();
if (pq.size() < k)
return -1;
return pq.peek();
}
}
public class Main {
public static void main(String[] args) {
KthLargest obj = new KthLargest(3);
System.out.println(obj.add(4));
System.out.println(obj.add(5));
System.out.println(obj.add(8));
System.out.println(obj.add(2));
System.out.println(obj.add(10));
}
}
JavaScript
class MinHeap {
constructor() {
this.data = [];
}
push(val) {
this.data.push(val);
this.data.sort((a, b) => a - b);
}
pop() {
return this.data.shift();
}
top() {
return this.data[0];
}
size() {
return this.data.length;
}
}
class KthLargest {
constructor(k) {
this.k = k;
this.heap = new MinHeap();
}
add(val) {
this.heap.push(val);
if (this.heap.size() > this.k)
this.heap.pop();
if (this.heap.size() < this.k)
return -1;
return this.heap.top();
}
}
// Driver Code
let obj = new KthLargest(3);
console.log(obj.add(4));
console.log(obj.add(5));
console.log(obj.add(8));
console.log(obj.add(2));
console.log(obj.add(10));
C#
using System;
using System.Collections.Generic;
class KthLargest {
int k;
PriorityQueue pq;
public KthLargest(int k) {
this.k = k;
pq = new PriorityQueue();
}
public int Add(int val) {
pq.Enqueue(val, val);
if (pq.Count > k)
pq.Dequeue();
if (pq.Count < k)
return -1;
return pq.Peek();
}
}
class Program {
static void Main() {
KthLargest obj = new KthLargest(3);
Console.WriteLine(obj.Add(4));
Console.WriteLine(obj.Add(5));
Console.WriteLine(obj.Add(8));
Console.WriteLine(obj.Add(2));
Console.WriteLine(obj.Add(10));
}
}
Output
-1
-1
4
4
5
Final Summary
| Approach | Recommendation |
|---|---|
| Brute Force | Not interview-friendly |
| Max Heap | Conceptual only |
| Min Heap (size k) | Interview standard |
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.jpg)
.jpg)
.jpg)
.png)
