Kth largest in a stream

Lesson 8.3 · Medium · Top-k · 10 min · by Vinay C

We'll cover the following

Overview
Watch it run
The idea
Complexity
In Python
Summary

Numbers arrive one at a time. Keep only the k largest seen so far and report the kth largest.

Watch it run

Press Play or Step to walk through the example, or change the input and press Run. Each frame says what the algorithm does and why.

in50

121

193

215

157

279

410

1811

1112

3013

614

1415

The heap has room (1 of 4). Keep 5.

kept (smallest first) [5]

1 / 17

The idea

Complexity

Time	Space	Why
`O(n log k)`	`O(k)`	The heap never holds more than k items.

In Python

import heapq
def kth_largest(nums, k):
    h = []
    for x in nums:
        if len(h) < k: heapq.heappush(h, x)
        elif x > h[0]: heapq.heapreplace(h, x)
    return h[0]

Try it on LeetCode: Kth Largest Element in a Stream →

Summary: say it in the interview

Keep a min-heap of size k. The smallest of the k largest sits at the root. A new value only matters if it beats that root, so replace it. Memory stays at k even for a huge stream.
Time O(n log k), space O(k). The heap never holds more than k items.