703. Kth Largest Element in a Stream (Easy)

Problem

Design a class that efficiently returns the k-th largest element in a stream of integers:

KthLargest(k, nums), initialize with a starting stream.
add(val), add val and return the current kth largest.

Example

k = 3, nums = [4, 5, 8, 2]
add(3)   // 4
add(5)   // 5
add(10)  // 5
add(9)   // 8
add(4)   // 8

LeetCode 703 · Link · Easy

Try it yourself

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run Go to execute. Runs via the Go Playground API.

Approach 1: Brute force, sort on every add

Keep a sorted list; on each add, insert and return list[-k].

import bisect

class KthLargest:
    def __init__(self, k, nums):
        self.k = k
        self.nums = sorted(nums)       # L1: O(n log n) initial sort

    def add(self, val):
        bisect.insort(self.nums, val)  # L2: O(log n) find + O(n) shift
        return self.nums[-self.k]      # L3: O(1) index

class KthLargest {
    private k: number;
    private nums: number[];

    constructor(k: number, nums: number[]) {
        this.k = k;
        this.nums = [...nums].sort((a, b) => a - b);  // L1: O(n log n) initial sort
    }

    add(val: number): number {
        // Binary search for insertion point, then splice
        let lo = 0, hi = this.nums.length;
        while (lo < hi) {
            const mid = (lo + hi) >> 1;
            if (this.nums[mid] < val) lo = mid + 1;
            else hi = mid;
        }
        this.nums.splice(lo, 0, val);          // L2: O(log n) find + O(n) shift
        return this.nums[this.nums.length - this.k];  // L3: O(1) index
    }
}

final class KthLargest {
    private let k: Int
    private var values: [Int]
    init(_ k: Int, _ nums: [Int]) { self.k = k; values = nums }
    func add(_ val: Int) -> Int { values.append(val); values.sort(by: >); return values[k - 1] }
}

Where the time goes, line by line

Variables: n = number of elements seen so far, k = the rank parameter.

Line	Per-call cost	Times executed	Contribution
L1 (initial sort)	$O(n log n)$	1 (init)	$O(n log n)$
L2 (insort / splice)	$O(n)$	1 per add	$O(n)$ ← dominates each add
L3 (index)	$O(1)$	1 per add	$O(1)$

bisect.insort / splice finds the insertion point in $O(log n)$ but must shift all subsequent elements in $O(n)$ .

Complexity

add: $O(n)$ per call (L2 shift dominates).
Space: $O(n)$ .

Approach 2: Keep a full heap

Maintain a max-heap of all values. On each add, push, then pop the top k-1 to peek the kth, then put them back.

import heapq

class KthLargest:
    def __init__(self, k, nums):
        self.k = k
        self.max_heap = [-x for x in nums]
        heapq.heapify(self.max_heap)                 # L1: O(n) build

    def add(self, val):
        heapq.heappush(self.max_heap, -val)          # L2: O(log n)
        popped = []
        for _ in range(self.k - 1):                   # L3: pop k-1 largest
            popped.append(heapq.heappop(self.max_heap))
        result = -self.max_heap[0]                    # L4: peek the kth
        for x in popped:
            heapq.heappush(self.max_heap, x)          # L5: put them back
        return result

// Full max-heap approach -- kept for comparison. Each add is O(k log n),
// worse than the size-K min-heap (Approach 3) which is O(log k).
// Implementation omitted; see Approach 3 for the optimal version.

final class KthLargest {
    private let k: Int
    private var heap = BinaryHeap<Int>(hasHigherPriority: >)
    init(_ k: Int, _ nums: [Int]) { self.k = k; for value in nums { heap.insert(value) } }
    func add(_ val: Int) -> Int { heap.insert(val); var copy = heap; var answer = 0; for _ in 0..<k { answer = copy.removeRoot()! }; return answer }
}

This works but each add is $O(k log n)$ , worse than the size-K heap (Approach 3) which is $O(log k)$ . The “full heap” stores everything you’ve ever seen ( $O(n)$ space) instead of just the K candidates.

The meaningful optimization is Approach 3.

Approach 3: Size-K min-heap (optimal)

Maintain a min-heap of size K. The top is always the current kth largest. On add, push and pop-if-oversized.

import heapq

class KthLargest:
    def __init__(self, k: int, nums: list[int]):
        self.k = k
        self.heap = []
        for x in nums:
            self.add(x)              # L1: O(log k) per initial element

    def add(self, val: int) -> int:
        if len(self.heap) < self.k:
            heapq.heappush(self.heap, val)      # L2: O(log k) push
        elif val > self.heap[0]:
            heapq.heapreplace(self.heap, val)   # L3: O(log k) pop+push atomic
        return self.heap[0]                     # L4: O(1) peek top

class MinHeap {
    private data: number[] = [];
    get size(): number { return this.data.length; }
    get top(): number { return this.data[0]; }
    push(val: number): void {
        this.data.push(val);
        this._siftUp(this.data.length - 1);
    }
    pop(): number {
        const top = this.data[0];
        const last = this.data.pop()!;
        if (this.data.length > 0) { this.data[0] = last; this._siftDown(0); }
        return top;
    }
    // Pop top then push val in one sift -- like heapreplace
    replace(val: number): void {
        this.data[0] = val;
        this._siftDown(0);
    }
    private _siftUp(i: number): void {
        while (i > 0) {
            const p = (i - 1) >> 1;
            if (this.data[p] <= this.data[i]) break;
            [this.data[p], this.data[i]] = [this.data[i], this.data[p]]; i = p;
        }
    }
    private _siftDown(i: number): void {
        const n = this.data.length;
        while (true) {
            let smallest = i;
            const l = 2 * i + 1, r = 2 * i + 2;
            if (l < n && this.data[l] < this.data[smallest]) smallest = l;
            if (r < n && this.data[r] < this.data[smallest]) smallest = r;
            if (smallest === i) break;
            [this.data[smallest], this.data[i]] = [this.data[i], this.data[smallest]]; i = smallest;
        }
    }
}

class KthLargest {
    private heap = new MinHeap();
    private k: number;

    constructor(k: number, nums: number[]) {
        this.k = k;
        for (const x of nums) this.add(x);   // L1: O(log k) per initial element
    }

    add(val: number): number {
        if (this.heap.size < this.k) {
            this.heap.push(val);              // L2: O(log k) push
        } else if (val > this.heap.top) {
            this.heap.replace(val);           // L3: O(log k) pop+push atomic
        }
        return this.heap.top;               // L4: O(1) peek top
    }
}

package main

import (
    "container/heap"
    "fmt"
)

type MinHeap []int
func (h MinHeap) Len() int            { return len(h) }
func (h MinHeap) Less(i, j int) bool  { return h[i] < h[j] }
func (h MinHeap) Swap(i, j int)       { h[i], h[j] = h[j], h[i] }
func (h *MinHeap) Push(x any)         { *h = append(*h, x.(int)) }
func (h *MinHeap) Pop() any {
    old := *h; n := len(old); x := old[n-1]; *h = old[:n-1]; return x
}

type KthLargest struct {
    k    int
    heap *MinHeap
}

func Constructor(k int, nums []int) KthLargest {
    h := &MinHeap{}
    heap.Init(h)
    kl := KthLargest{k: k, heap: h}
    for _, x := range nums { kl.Add(x) } // L1: O(log k) per initial element
    return kl
}

func (kl *KthLargest) Add(val int) int {
    if kl.heap.Len() < kl.k {
        heap.Push(kl.heap, val) // L2: O(log k) push
    } else if val > (*kl.heap)[0] {
        heap.Pop(kl.heap)
        heap.Push(kl.heap, val) // L3: O(log k) pop+push
    }
    return (*kl.heap)[0] // L4: O(1) peek top
}

func assert(condition bool, msgs ...string) {
    if !condition { msg := "assertion failed"; if len(msgs) > 0 { msg = msgs[0] }; panic(msg) }
}

func runTests() {
    kl := Constructor(3, []int{4, 5, 8, 2})
    assert(kl.Add(3) == 4); assert(kl.Add(5) == 5); assert(kl.Add(10) == 5)
    assert(kl.Add(9) == 8); assert(kl.Add(4) == 8)
    kl2 := Constructor(1, []int{})
    assert(kl2.Add(3) == 3); assert(kl2.Add(5) == 5); assert(kl2.Add(1) == 5)
    kl3 := Constructor(2, []int{1, 2})
    assert(kl3.Add(0) == 1); assert(kl3.Add(3) == 2)
    fmt.Println("all tests pass")
}

func main() { runTests() }

final class KthLargest {
    private let k: Int
    private var heap = BinaryHeap<Int>(hasHigherPriority: <)
    init(_ k: Int, _ nums: [Int]) { self.k = k; for value in nums { heap.insert(value); if heap.count > k { _ = heap.removeRoot() } } }
    func add(_ val: Int) -> Int { heap.insert(val); if heap.count > k { _ = heap.removeRoot() }; return heap.peek! }
}

Where the time goes, line by line

Variables: n = number of initial elements in nums, k = the rank parameter.

Line	Per-call cost	Times executed	Contribution
L1 (init loop)	$O(log k)$	n	$O(n log k)$
L2 or L3 (push/replace)	$O(log k)$	1 per add	$O(log k)$ ← dominates each add
L4 (peek)	$O(1)$	1 per add	$O(1)$

The heap never grows beyond k entries. heapreplace / replace is one sift-down operation, cheaper than a separate heappop + heappush because it avoids an extra sift-up.

Complexity

add: $O(log k)$ per call (L2 or L3).
Space: $O(k)$ .

Why min-heap?

A min-heap of size K holds the K largest seen; the smallest of those K sits at the top and is, by definition, the Kth largest overall. When a new value arrives, it only matters if it’s larger than the current min (otherwise it can’t be in the top K).

heapreplace / replace pops and pushes in one operation, cheaper than push + pop as separate calls.

Try this approach:

TypeScript
Go

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Click Run Go to execute. Runs via the Go Playground API.

# Quick smoke tests, paste into a REPL or save as test_703.py and run.
# Uses the size-K min-heap approach (Approach 3).
import heapq

class KthLargest:
    def __init__(self, k, nums):
        self.k = k
        self.heap = []
        for x in nums:
            self.add(x)

    def add(self, val):
        if len(self.heap) < self.k:
            heapq.heappush(self.heap, val)
        elif val > self.heap[0]:
            heapq.heapreplace(self.heap, val)
        return self.heap[0]

def _run_tests():
    # Example from problem statement: k=3, nums=[4,5,8,2]
    kl = KthLargest(3, [4, 5, 8, 2])
    assert kl.add(3) == 4
    assert kl.add(5) == 5
    assert kl.add(10) == 5
    assert kl.add(9) == 8
    assert kl.add(4) == 8

    # k=1: always return max
    kl2 = KthLargest(1, [])
    assert kl2.add(3) == 3
    assert kl2.add(5) == 5
    assert kl2.add(1) == 5

    # k equals initial size
    kl3 = KthLargest(2, [1, 2])
    assert kl3.add(0) == 1   # 3rd largest among [1,2,0] would be 0; kth=2nd=1
    assert kl3.add(3) == 2   # [0,1,2,3] kth=2nd=2

    print("all tests pass")

if __name__ == "__main__":
    _run_tests()

// Uses the size-K min-heap approach (Approach 3).
// See 703-kth-largest-element-in-stream-approach3.ts for the full implementation.
const kl = new KthLargest(3, [4, 5, 8, 2]);
console.assert(kl.add(3) === 4);
console.assert(kl.add(5) === 5);
console.assert(kl.add(10) === 5);
console.assert(kl.add(9) === 8);
console.assert(kl.add(4) === 8);

const kl2 = new KthLargest(1, []);
console.assert(kl2.add(3) === 3);
console.assert(kl2.add(5) === 5);
console.assert(kl2.add(1) === 5);

const kl3 = new KthLargest(2, [1, 2]);
console.assert(kl3.add(0) === 1);
console.assert(kl3.add(3) === 2);

console.log("all tests pass");

Summary

Approach	`add`	Space
Sorted list (insort)	$O(n)$	$O(n)$
Size-K min-heap	$O(log k)$	$O(k)$

This is the canonical “top-K streaming” pattern; the same template solves Top K Frequent (347) online and streaming percentile problems.

Heaps / Priority Queues, size-K min-heap for online top-K

Top K, the selection pattern for keeping only the best K items instead of sorting everything.
Heap and Priority Queue, the priority frontier for repeatedly taking the smallest, largest, or most urgent item.