Kth Largest Number in a Stream (Maintain the Kth Largest as Numbers Arrive)

• Kth Largest in a Stream – a design problem where a class must report the Kth largest number seen so far each time a new number arrives.
• Min-heap of size K – holds the K largest numbers; its root is the smallest of those K, which is the Kth largest overall.
• Add operation – offer the number, trim the heap to size K by polling the root if it grew, and return the root as the current Kth largest.
• Constructor – seeds the initial numbers through the same add path so the heap self-limits to K.
• Complexity – O(log K) per add, O(K) space regardless of stream length.

What is the Kth Largest in a Stream problem?

This is LeetCode 703. You design a class that accepts a stream of numbers one at a time. After each addition, the class must return the Kth largest number among all numbers seen so far. The initial constructor receives K and an optional seed list of numbers.

The challenge is efficiency: you cannot re-sort the entire history on every add call.

package com.bank.service;

// KthLargest class with K=3 and initial = [4, 5, 8, 2]
// add(3) -> returns 4  (sorted: [2,3,4,5,8], 3rd largest = 4? No wait.)
// Let me trace: [2,3,4,5,8]. 3rd largest = 5. Check the heap.
// Heap after init: [4, 5, 8] (K=3, root=4? No, min-heap root=4)
// Wait: after seeding [4,5,8,2] with K=3:
//   add(4) -> heap [4], size=1
//   add(5) -> heap [4,5], size=2
//   add(8) -> heap [4,5,8], size=3
//   add(2) -> heap [2,4,5,8], size=4>3, poll 2 -> heap [4,5,8], root=4
// add(3) -> heap [3,4,5,8], size=4>3, poll 3 -> heap [4,5,8], root=4
// 3rd largest of [2,3,4,5,8] is 5. But root is 4.
// Actually: 3rd largest of [2,3,4,5,8] = 5 (8,5,4 are the 3 largest, 3rd is 4)
// 8 is 1st largest, 5 is 2nd largest, 4 is 3rd largest. Root=4. Correct!

How does the min-heap of size K work?

The class holds a PriorityQueue (min-heap) and the value K. The heap always contains at most K elements, which are the K largest numbers seen so far. Because it is a min-heap, its root is the smallest of those K, which is exactly the Kth largest overall.

package com.bank.service;

import java.util.PriorityQueue;

public class KthLargestStream {
    private final PriorityQueue<Integer> minHeap;
    private final int k;

    public KthLargestStream(int k, int[] initial) {
        this.k = k;
        this.minHeap = new PriorityQueue<>();
        for (int num : initial) {
            add(num);
        }
    }

    public int add(int num) {
        minHeap.offer(num);
        if (minHeap.size() > k) {
            minHeap.poll(); // remove the smallest, keeping K largest
        }
        return minHeap.peek(); // root = Kth largest
    }
}

How does the add method maintain correctness?

When a new number arrives, you offer it to the heap. If the heap now has more than K elements, you poll the root (the smallest in the heap). This either evicts the number you just added (if it was too small to be in the top K) or evicts the old Kth largest (if the new number is large enough to enter the top K). Either way, the heap is back to size K and its root is the current Kth largest.

package com.bank.service;

public class StreamDemo {
    public static void main(String[] args) {
        int[] initialAmounts = {400, 500, 800, 200};
        KthLargestStream tracker = new KthLargestStream(3, initialAmounts);
        // After seeding: heap = [400, 500, 800], root = 400
        // (200 was polled because heap exceeded K=3)

        System.out.println(tracker.add(300)); // heap tries [300,400,500,800]
        // poll 300 -> heap [400,500,800], root = 400

        System.out.println(tracker.add(900)); // heap tries [400,500,800,900]
        // poll 400 -> heap [500,800,900], root = 500

        System.out.println(tracker.add(100)); // heap tries [100,500,800,900]
        // poll 100 -> heap [500,800,900], root = 500
    }
}

400
500
500

Why seed through the add method?

The constructor seeds the initial numbers through the same add routine so there is only one place that enforces the size limit. This avoids duplicated logic and ensures the heap is correctly trimmed to K after initialization. A common mistake is writing separate logic for the constructor and the add method, which introduces subtle bugs when the initial list has fewer than K elements.

// CORRECT: reuse the add method
public KthLargestStream(int k, int[] initial) {
    this.k = k;
    this.minHeap = new PriorityQueue<>();
    for (int num : initial) {
        add(num); // same path, same size enforcement
    }
}

How is this different from Kth Smallest in a Stream?

For Kth largest you use a min-heap of size K. For Kth smallest you use a max-heap of size K. The root always represents the boundary.

| Feature | Kth Largest in Stream | Kth Smallest in Stream |
|---|---|---|
| Heap type | Min-heap (size K) | Max-heap (size K) |
| Heap contents | K largest numbers | K smallest numbers |
| Root meaning | Smallest of K largest = Kth largest | Largest of K smallest = Kth smallest |
| Eviction | Evict when too small for top K | Evict when too large for bottom K |

What are the edge cases?

• K equals 1: the heap holds only one element, the maximum. Every add replaces it only if the new number is larger.
• K equals stream length: the heap holds all elements. The root is the minimum, which is the Kth largest when K = n.
• Fewer than K initial elements: the heap has fewer than K elements until enough adds arrive. In this state, peek() returns the minimum of all numbers seen.
• All identical numbers: the heap fills with duplicates. The Kth largest is the same number.

package com.bank.service;

public class EdgeCaseDemo {
    public static void main(String[] args) {
        // K=1: always tracks the max
        KthLargestStream maxTracker = new KthLargestStream(1, new int[]{5, 3, 8});
        System.out.println("K=1: " + maxTracker.add(6)); // 8

        // Fewer than K initial elements
        KthLargestStream sparse = new KthLargestStream(3, new int[]{5});
        System.out.println("Sparse add(2): " + sparse.add(2)); // heap has [2,5], root=2
    }
}

K=1: 8
Sparse add(2): 2

What about the banking use case?

At the National Bank of India, the real-time monitoring dashboard tracks all incoming transfer amounts and must always display the Kth largest amount as a threshold indicator. If the Kth largest suddenly drops, it signals a lull in high-value activity. If it spikes, it signals a surge. The dashboard uses a min-heap of size K so each new amount costs only O(log K) and the memory stays fixed at K entries regardless of how many transfers flow through.

package com.bank.service;

import java.math.BigDecimal;
import java.util.PriorityQueue;

public class TransactionThresholdTracker {
    private final PriorityQueue<BigDecimal> minHeap;
    private final int k;

    public TransactionThresholdTracker(int k) {
        this.k = k;
        this.minHeap = new PriorityQueue<>();
    }

    public BigDecimal addTransaction(BigDecimal amount) {
        minHeap.offer(amount);
        if (minHeap.size() > k) {
            minHeap.poll();
        }
        return minHeap.peek();
    }

    public static void main(String[] args) {
        TransactionThresholdTracker tracker = new TransactionThresholdTracker(3);
        String[] amounts = {"50000", "120000", "75000", "200000", "30000"};
        for (String amt : amounts) {
            BigDecimal threshold = tracker.addTransaction(new BigDecimal(amt));
            System.out.println("After " + amt + " -> 3rd largest: " + threshold);
        }
    }
}

After 50000 -> 3rd largest: 50000
After 120000 -> 3rd largest: 50000
After 75000 -> 3rd largest: 50000
After 200000 -> 3rd largest: 75000
After 30000 -> 3rd largest: 75000

What should a senior engineer know?

• Constant memory: the heap holds exactly K entries no matter how long the stream runs. This is the core scalability property.
• Not a batch operation: this is a streaming design. Quickselect is better for a one-shot query on static data.
• Thread safety: in production, wrap the add method in a synchronized block or use a concurrent data structure.
• Generic version: replace int with a Comparable or accept a Comparator for custom ordering.
• Distributed streams: in a multi-node scenario, each node maintains a local top-K heap and a coordinator merges them periodically.

What are common interview follow-up questions?

• What is the time complexity of add? (O(log K) for the heap offer and optional poll.)
• What is the space complexity? (O(K) regardless of stream length.)
• What happens if fewer than K numbers have been added? (The root is the minimum of all numbers seen.)
• How would you modify it for the Kth smallest in a stream? (Use a max-heap of size K.)
• Can you do this without a heap? (A balanced BST or sorted list works but with worse constants.)