Definition
- Min-heap of size K – holds the K largest values encountered so far.
- Root is the answer – the smallest among the K largest is by definition the Kth largest overall.
- Trim on add – push the new value; if the heap exceeds K, poll the minimum to keep exactly K entries.
- O(log K) per add – one push and at most one poll, each O(log K).
- O(K) memory – the heap never grows beyond K, regardless of stream length.
Imagine always knowing the fifth-largest donation received so far at the National Bank of India's charity event as donations keep arriving. You keep a shortlist of exactly the five biggest. When a new donation comes, you add it to the shortlist and, if the list grew to six, you drop the smallest. The smallest on that shortlist of five is always the fifth-largest overall.
Understanding the Concepts
What is the problem?
Design a class that is initialized with a value K and an initial list of numbers. It supports an add operation that inserts a new number and returns the Kth largest element among all numbers seen so far.
package com.bank.sort;
import java.util.PriorityQueue;
public class KthLargestStream {
private final int k;
private final PriorityQueue<Integer> minHeap;
public KthLargestStream(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(); // remove the smallest
}
return minHeap.peek(); // root is the Kth largest
}
public static void main(String[] args) {
int[] initial = {40000, 50000, 20000, 80000, 10000};
KthLargestStream stream = new KthLargestStream(3, initial);
// K=3, initial heap after seeding: [40000, 50000, 80000]
System.out.println("Add 30000: " + stream.add(30000)); // 40000
System.out.println("Add 60000: " + stream.add(60000)); // 50000
System.out.println("Add 90000: " + stream.add(90000)); // 60000
}
}
Add 30000: 40000
Add 60000: 50000
Add 90000: 60000
Why does a min-heap of size K work?
The heap always holds exactly the K largest values seen. The root is the smallest of these K, which is the Kth largest overall. When a new value arrives, if it is larger than the root it should enter the top-K, pushing out the current root. The offer/poll logic handles this automatically.
package com.bank.sort;
import java.util.PriorityQueue;
public class WhyMinHeap {
public static void main(String[] args) {
PriorityQueue<Integer> heap = new PriorityQueue<>();
int k = 3;
int[] stream = {50, 80, 20, 40, 90, 10, 70};
for (int val : stream) {
heap.offer(val);
if (heap.size() > k) heap.poll();
System.out.println("Add " + val + ": heap=" + heap
+ " Kth=" + heap.peek());
}
}
}
Add 50: heap=[50] Kth=50
Add 80: heap=[50, 80] Kth=50
Add 20: heap=[20, 80, 50] Kth=20
Add 40: heap=[40, 80, 50] Kth=40
Add 90: heap=[50, 90, 80] Kth=50
Add 10: heap=[50, 90, 80] Kth=50
Add 70: heap=[70, 90, 80] Kth=70
How does the constructor seed the heap?
The constructor feeds the initial numbers through the same add logic. This ensures the heap settles into holding the K largest from the start.
package com.bank.sort;
import java.util.PriorityQueue;
public class ConstructorSeeding {
public static void main(String[] args) {
PriorityQueue<Integer> heap = new PriorityQueue<>();
int k = 3;
int[] initial = {50000, 20000, 80000, 10000, 40000};
for (int num : initial) {
heap.offer(num);
if (heap.size() > k) heap.poll();
}
System.out.println("Heap after seeding: " + heap);
System.out.println("Kth largest: " + heap.peek());
}
}
Heap after seeding: [40000, 80000, 50000]
Kth largest: 40000
What happens when fewer than K values have been seen?
When fewer than K values exist, the heap holds all of them and its root is the smallest of whatever has been seen. This is the correct Kth largest for the current count, or you can define it as the smallest value.
package com.bank.sort;
import java.util.PriorityQueue;
public class FewerThanK {
public static void main(String[] args) {
PriorityQueue<Integer> heap = new PriorityQueue<>();
int k = 5;
int[] values = {30, 10, 20};
for (int v : values) {
heap.offer(v);
if (heap.size() > k) heap.poll();
System.out.println("Add " + v + ": size=" + heap.size()
+ " root=" + heap.peek());
}
}
}
Add 30: size=1 root=30
Add 10: size=2 root=10
Add 20: size=3 root=10
What is the time and space complexity?
| Operation | Time | Space |
|---|---|---|
| Constructor | O(n log K) for n initial elements | O(K) |
| add | O(log K) | O(K) |
| peek (query) | O(1) | O(K) |
How is this different from sorting the entire stream?
Sorting the entire stream to find the Kth largest would take O(n log n) per query and O(n) memory. The heap approach answers each add in O(log K) and uses only O(K) memory, which is bounded regardless of stream length.
| Approach | Time per add | Memory |
|---|---|---|
| Sort all | O(n log n) | O(n) |
| Min-heap K | O(log K) | O(K) |
| Quickselect | O(n) avg | O(n) |
How is this used in a banking system?
At the National Bank of India, a fraud dashboard shows the Kth largest transaction amount as a live high-value watermark that updates with every incoming transaction. The size-K min-heap lets the dashboard respond to each new amount in O(log K) time while holding only K values.
package com.bank.sort;
import java.math.BigDecimal;
import java.util.PriorityQueue;
public class FraudDashboard {
private final int k;
private final PriorityQueue<BigDecimal> heap;
public FraudDashboard(int k) {
this.k = k;
this.heap = new PriorityQueue<>();
}
public BigDecimal addTransaction(BigDecimal amount) {
heap.offer(amount);
if (heap.size() > k) heap.poll();
return heap.peek();
}
public static void main(String[] args) {
FraudDashboard dashboard = new FraudDashboard(3);
String[] txns = {"50000", "80000", "20000", "90000", "60000"};
for (String t : txns) {
BigDecimal amt = new BigDecimal(t);
BigDecimal kth = dashboard.addTransaction(amt);
System.out.println("Txn " + t + " -> 3rd largest: " + kth);
}
}
}
Txn 50000 -> 3rd largest: 50000
Txn 80000 -> 3rd largest: 50000
Txn 20000 -> 3rd largest: 20000
Txn 90000 -> 3rd largest: 50000
Txn 60000 -> 3rd largest: 60000
What are common interview follow-up questions?
- Interviewers often extend this problem:
- What if K changes dynamically? (Adjust the heap size.)
- How do you find both Kth largest and Kth smallest? (Two heaps.)
- How does this relate to the median-finding problem? (Two heaps: max-heap for lower half, min-heap for upper half.)
Visual Overview
Min-Heap of Size K=3:
Stream: 50, 80, 20, 40, 90
After 50: [50] Kth = 50
After 80: [50, 80] Kth = 50
After 20: [20, 80, 50] Kth = 20 (heap has 3)
After 40: offer 40, poll 20
[40, 80, 50] Kth = 40
After 90: offer 90, poll 40
[50, 90, 80] Kth = 50
Heap always holds K=3 largest: root = Kth largest
Key Takeaway
Kth Largest in a Stream asks you to return the Kth largest value among everything seen so far as new values arrive. The solution is a min-heap capped at size K that always holds exactly the K largest values. Its root, the smallest of those K, is by definition the Kth largest overall.
The add operation pushes the new value and, if the heap then exceeds K, polls the minimum to trim back. After that, the root is the answer in O(1). The constructor seeds the heap by feeding initial values through the same add logic. Each add is O(log K), and memory stays at O(K) regardless of stream length.
In a banking system at the National Bank of India, a fraud dashboard shows the Kth largest transaction as a live watermark. The min-heap answers each incoming transaction in logarithmic time while holding only K values, keeping the watermark current without growing memory.
This is the canonical pattern for streaming top-K queries. It avoids storing the entire history and handles unbounded streams efficiently.
Remember one sentence: a size-K min-heap holds the K largest values seen, and its root is always the Kth largest, updated in O(log K) per new element.
---