703. Kth Largest Element in a Stream

Quick Identifier

Topic: heap-priority-queue
Pattern: Top-K / Heap
Difficulty: Easy
Companies: Amazon, Google, Meta, Microsoft, Bloomberg
Frequency: High
LeetCode: 703

Quick Sights

Time Complexity: k from the optimal approach.
Space Complexity: O(log k) from the optimal approach.
Core Mechanism: After construction with an integer k and an initial array, each add(val) appends a value and returns the current kth largest element among all numbers seen so far. Output is always the kth largest in the maintained multiset.

After construction with an integer k and an initial array, each add(val) appends a value and returns the current kth largest element among all numbers seen so far. Output is always the kth largest in the maintained multiset.

State the invariant before coding: what partial result is already correct, what work remains, and what value or state each recursive/iterative step must preserve.

Recognition cues:

"kth largest" in a streaming setting with repeated inserts
Need only the kth largest, not full sorting
Heap size should stay bounded by k, not grow with stream length

Study Pattern (SDE3+)

0-3 min: restate I/O and brittle edges aloud, then verbalize two approaches with time/space before you touch the keyboard.
Implementation pass: one-line invariant above the tight loop; state what progress you make each iteration.
5 min extension: pick one constraint twist (immutable input, stream, bounded memory, parallel readers) and explain what in your solution breaks without a refactor.

Diagram

This diagram shows the algorithm movement for this problem family.

Loading diagram…

Approaches

Brute force — sort entire collection after each add — O(n log n) per add / O(n) space — too slow for many adds.
Better — maintain sorted structure or multiset — still heavy per update.
Optimal — min-heap of size exactly k holding the k largest values seen; heap root is the kth largest — O(log k) per add, O(k) space.

Optimal Solution

Go

import (
	"container/heap"
)

type IntMinHeap []int

func (heapSlice IntMinHeap) Len() int           { return len(heapSlice) }
func (heapSlice IntMinHeap) Less(left, right int) bool {
	return heapSlice[left] < heapSlice[right]
}
func (heapSlice IntMinHeap) Swap(left, right int) {
	heapSlice[left], heapSlice[right] = heapSlice[right], heapSlice[left]
}

func (heapSlice *IntMinHeap) Push(value any) {
	*heapSlice = append(*heapSlice, value.(int))
}

func (heapSlice *IntMinHeap) Pop() any {
	old := *heapSlice
	length := len(old)
	value := old[length-1]
	*heapSlice = old[0 : length-1]
	return value
}

type KthLargest struct {
	threshold int
	minHeap   *IntMinHeap
}

func Constructor(k int, nums []int) KthLargest {
	minHeap := &IntMinHeap{}
	heap.Init(minHeap)
	for _, num := range nums {
		heap.Push(minHeap, num)
		for minHeap.Len() > k {
			heap.Pop(minHeap)
		}
	}
	return KthLargest{threshold: k, minHeap: minHeap}
}

func (receiver *KthLargest) Add(value int) int {
	heap.Push(receiver.minHeap, value)
	for receiver.minHeap.Len() > receiver.threshold {
		heap.Pop(receiver.minHeap)
	}
	return (*receiver.minHeap)[0]
}

JavaScript

class MinHeap {
  constructor() {
    this.data = [];
  }

  size() {
    return this.data.length;
  }

  peek() {
    return this.data[0];
  }

  push(value) {
    this.data.push(value);
    this.bubbleUp(this.data.length - 1);
  }

  pop() {
    if (this.data.length === 0) {
      return undefined;
    }
    const top = this.data[0];
    const last = this.data.pop();
    if (this.data.length > 0) {
      this.data[0] = last;
      this.bubbleDown(0);
    }
    return top;
  }

  bubbleUp(index) {
    while (index > 0) {
      const parentIndex = Math.floor((index - 1) / 2);
      if (this.data[index] >= this.data[parentIndex]) {
        break;
      }
      this.swap(index, parentIndex);
      index = parentIndex;
    }
  }

  bubbleDown(index) {
    const length = this.data.length;
    while (true) {
      const leftChild = index * 2 + 1;
      const rightChild = index * 2 + 2;
      let smallest = index;
      if (leftChild < length && this.data[leftChild] < this.data[smallest]) {
        smallest = leftChild;
      }
      if (rightChild < length && this.data[rightChild] < this.data[smallest]) {
        smallest = rightChild;
      }
      if (smallest === index) {
        break;
      }
      this.swap(index, smallest);
      index = smallest;
    }
  }

  swap(leftIndex, rightIndex) {
    const temp = this.data[leftIndex];
    this.data[leftIndex] = this.data[rightIndex];
    this.data[rightIndex] = temp;
  }
}

class KthLargest {
  constructor(k, nums) {
    this.threshold = k;
    this.minHeap = new MinHeap();
    for (const num of nums) {
      this.minHeap.push(num);
      while (this.minHeap.size() > k) {
        this.minHeap.pop();
      }
    }
  }

  add(value) {
    this.minHeap.push(value);
    while (this.minHeap.size() > this.threshold) {
      this.minHeap.pop();
    }
    return this.minHeap.peek();
  }
}

Walkthrough

k = 3, nums = [4, 5, 8, 2]. Build min-heap, keep size 3: largest three are 8, 5, 4 → min-heap root = 4 (3rd largest).

step	action	k largest (concept)	min-heap root	return
after init	among 2,4,5,8 keep top 3	8, 5, 4	4	—
add(5)	add 5; still top three 8,5,5	8, 5, 5	5	5

Invariant: Min-heap of size at most k contains exactly the k largest stream values; root is the kth largest.

Edge Cases

k === 1: heap holds one element; every add replaces tracking of maximum behavior via heap of size 1
Initial array shorter than k: heap has fewer than k elements until enough adds; problem guarantees stream fills—check problem statement for API contract (often initial length can be less than k)
Duplicate values: heap handles duplicates as separate entries

Pitfalls

Using a max-heap of all elements — blows memory and time
Popping wrong element — must pop from min-heap when maintaining k largest
Off-by-one on heap size after each add

Variants

Kth smallest in stream → max-heap of size k
Sliding window kth largest → deque / two heaps (harder)

Mind-Map Tags

#heap #min-heap #top-k #streaming #kth-largest #container-heap