Kth Largest Element in a Stream

You keep getting new numbers. After each one you must say the kth largest so far. Not the largest. The kth largest. This sounds like you need the whole sorted list. But you do not. A small heap is all you need. The interviewer wants to see if you can hold just enough data and no more.

🎯 The Problem

You are given a number k, then numbers arrive one at a time and you report the kth largest so far.

The rules:

• After each new number, return the kth largest value seen so far.
• The kth largest sits in position k when you sort from biggest to smallest.
• If fewer than k numbers have arrived, there is no kth largest yet.

Input:  k = 3, then add 4, 5, 8, 2
Output: -inf, -inf, 4, 4

Explanation:
After 4        -> only 1 number, no 3rd largest yet
After 4, 5     -> only 2 numbers, no 3rd largest yet
After 4, 5, 8  -> sorted big to small [8, 5, 4] -> 3rd largest = 4
After 4, 5, 8, 2 -> [8, 5, 4, 2] -> 3rd largest = 4

So we never care about the very top values past k. We only care which value sits at rank k.

Here is the idea drawn as a flow. Each new number may or may not change the kth largest.

🐢 Approach 1: Sort Each Time (Brute Force)

The idea in one line: keep all numbers, sort big to small on each add, read index k - 1.

The idea:

• Store every number in a list.
• After each add, sort from biggest to smallest.
• Pick the value at index k - 1.

Why it is weak:

• Sorting on every add is O(n log n).
• A long stream makes that far too slow.
• You also keep every number, even ones far below rank k that can never be the answer.

Here is the sort-each-time code:

class KthLargest:
    def __init__(self, k, nums):
        self.k = k
        self.nums = nums

    def add(self, val):
        self.nums.append(val)
        return sorted(self.nums, reverse=True)[self.k - 1]

⚡ Approach 2: A Min-Heap of Size k (Best)

The idea in one line: keep only the top k numbers, with the kth largest sitting at the top.

The key insight:

• The kth largest value is the smallest of the top k values.
• So you only need to keep the top k numbers.
• Everything smaller than all of them is useless.

What a min-heap is:

• A min-heap is a binary tree kept in an array with the smallest value at the top.
• Reading the top is instant. Adding or removing is O(log n). It is also called a priority queue.

How it works:

• Keep a min-heap that holds at most k numbers.
• Push each new number.
• If the heap grows past k, pop the top. The top is the smallest, so you drop the weakest.
• What stays is still the top k, and the new top is the new kth largest.

Why it is fast:

• Each add is one push and maybe one pop, each O(log k).
• The heap never holds more than k numbers, so space stays O(k).

Here is the heap drawn as a tree after adding 4, 5, 8 with k equal to 3. The smallest, 4, sits at the top. That is our answer.

Steps to Solve

1. Make an empty min-heap. It will hold at most k numbers.
2. To add a number, push it onto the heap.
3. If the heap size is now greater than k, pop the top. That removes the smallest of the group.
4. The top of the heap is the kth largest so far. Return it.
5. If the heap has fewer than k numbers, there is no kth largest yet.

#include <stdio.h>

int heap[1000];
int heapSize = 0;

void push(int val) {
    int i = heapSize++;
    heap[i] = val;
    while (i > 0) {                  // bubble up, smallest goes to top
        int parent = (i - 1) / 2;
        if (heap[i] < heap[parent]) {
            int t = heap[i]; heap[i] = heap[parent]; heap[parent] = t;
            i = parent;
        } else break;
    }
}

void pop() {
    heap[0] = heap[--heapSize];      // move last to top
    int i = 0;
    while (1) {                      // bubble down
        int left = 2 * i + 1, right = 2 * i + 2, smallest = i;
        if (left < heapSize && heap[left] < heap[smallest]) smallest = left;
        if (right < heapSize && heap[right] < heap[smallest]) smallest = right;
        if (smallest == i) break;
        int t = heap[i]; heap[i] = heap[smallest]; heap[smallest] = t;
        i = smallest;
    }
}

int k = 3;

void add(int val) {
    push(val);
    if (heapSize > k) pop();         // keep only the top k numbers
    if (heapSize < k) printf("none\n");
    else printf("%d\n", heap[0]);    // top is the kth largest
}

int main(void) {
    add(4);
    add(5);
    add(8);
    add(2);
    return 0;
}

none
none
4
4

#include <iostream>
#include <queue>
#include <vector>
using namespace std;

priority_queue<int, vector<int>, greater<int>> heap;  // min-heap
int k = 3;

void add(int val) {
    heap.push(val);
    if ((int)heap.size() > k) heap.pop();   // keep only top k
    if ((int)heap.size() < k) cout << "none" << endl;
    else cout << heap.top() << endl;        // top is kth largest
}

int main() {
    add(4);
    add(5);
    add(8);
    add(2);
    return 0;
}

none
none
4
4

import java.util.PriorityQueue;

public class KthLargest {
    static PriorityQueue<Integer> heap = new PriorityQueue<>();  // min-heap
    static int k = 3;

    static void add(int val) {
        heap.offer(val);
        if (heap.size() > k) heap.poll();    // keep only top k
        if (heap.size() < k) System.out.println("none");
        else System.out.println(heap.peek()); // top is kth largest
    }

    public static void main(String[] args) {
        add(4);
        add(5);
        add(8);
        add(2);
    }
}

none
none
4
4

import heapq


class KthLargest:
    def __init__(self, k):
        self.k = k
        self.heap = []   # min-heap holding the top k numbers

    def add(self, val):
        heapq.heappush(self.heap, val)        # push the new number
        if len(self.heap) > self.k:
            heapq.heappop(self.heap)          # drop the smallest, keep top k
        if len(self.heap) < self.k:
            return None                       # not enough numbers yet
        return self.heap[0]                   # top is the kth largest


kl = KthLargest(3)
for num in [4, 5, 8, 2]:
    result = kl.add(num)
    print("none" if result is None else result)

none
none
4
4

class MinHeap {
  constructor() { this.data = []; }
  size() { return this.data.length; }
  top() { return this.data[0]; }
  push(val) {
    this.data.push(val);
    let i = this.data.length - 1;
    while (i > 0) {                       // bubble up
      const parent = (i - 1) >> 1;
      if (this.data[i] < this.data[parent]) {
        [this.data[i], this.data[parent]] = [this.data[parent], this.data[i]];
        i = parent;
      } else break;
    }
  }
  pop() {
    const last = this.data.pop();
    if (this.data.length > 0) {
      this.data[0] = last;
      let i = 0;
      while (true) {                      // bubble down
        let left = 2 * i + 1, right = 2 * i + 2, smallest = i;
        if (left < this.data.length && this.data[left] < this.data[smallest]) smallest = left;
        if (right < this.data.length && this.data[right] < this.data[smallest]) smallest = right;
        if (smallest === i) break;
        [this.data[i], this.data[smallest]] = [this.data[smallest], this.data[i]];
        i = smallest;
      }
    }
  }
}

const heap = new MinHeap();
const k = 3;

function add(val) {
  heap.push(val);
  if (heap.size() > k) heap.pop();    // keep only top k
  if (heap.size() < k) console.log("none");
  else console.log(heap.top());       // top is kth largest
}

add(4);
add(5);
add(8);
add(2);

none
none
4
4

Let us walk through the Python version line by line. The whole trick is keeping the heap small.

In __init__ we store k and start an empty list called heap. This list is a min-heap because we only ever touch it through heapq. So the smallest value stays at index 0.

In add, the first line pushes the new value with heapq.heappush. Now the heap may hold one too many. The if checks if the size went above k. If it did, heapq.heappop removes the smallest value. This is the important line. We always throw away the smallest, because the smallest of the group can never be the kth largest if we have more than k numbers.

After that, the heap holds the top k numbers, and the smallest of those is at the top. So self.heap[0] is exactly the kth largest. If we still have fewer than k numbers, there is no answer yet, so we return None.

The size never grows past k. So memory stays tiny even for a huge stream. That is the real win over keeping every number.

⏱️ Time and Space Complexity

The sort approach keeps all numbers and sorts on every add, which is O(n log n) per add. The heap approach keeps only k numbers. Each add does one push and maybe one pop, and each is O(log k). Reading the answer is O(1). So both time and space stay small and steady, no matter how long the stream runs.

🧩 Key Takeaways

• ✅ The kth largest value is the smallest of the top k values.
• ✅ A min-heap of size k holds the top k numbers, with the kth largest right at the top.
• ✅ When the heap grows past k, pop the smallest. That value can never be the answer.
• ✅ Each add is O(log k), and reading the answer is O(1).
• ✅ You only store k numbers, so memory stays small for any stream length.

🚀 What’s Next?

• Find Median from Data Stream
• Last Stone Weight