LeetCode 703 · Heap / Priority Queue

Kth Largest Element in a Stream, explained with a picture

A podium with k places as scores keep arriving.

EasyHeap / Priority Queue
▶ Watch it step by step

The problem

Design a class that, given k and some starting numbers, accepts new numbers one at a time and after each one returns the k-th largest number seen so far.

Input:  k = 3, start [4, 5, 8, 2], then add 3, 5, 10, 9, 4
Output: 4, 5, 5, 8, 8

Picture it

Picture a podium with exactly k places. It only ever keeps the top k scores. The lowest score still on the podium sits at the front (a min-heap keeps the smallest on top). When a new score arrives it climbs on; if that makes k + 1 people, the weakest steps off. The person at the front of the podium is the k-th largest.

How to recognise it

  • Numbers keep arriving and after each one you must report a rank statistic ("the k-th largest so far").
  • k is fixed, and only the top k items can ever matter. Everything below them can be forgotten.
  • You are asked for one value at a time, not the whole sorted list.
  • Up to about 10^4 starting numbers and 10^4 calls to add rule out re-sorting on every call.
  • Whenever you hear "top k" or "k-th best", think of a heap (a tree stored in a list that always keeps its smallest item at index 0, with O(log n) push and pop). A min-heap of size k keeps the k-th largest at the front.

Start with brute force

Keep every number in a list. On each add, append the new value, sort the list in descending order and read position k − 1.

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

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

Each call sorts up to about 2 × 10^4 numbers, roughly 3 × 10^5 steps. With 10^4 calls that is around 3 × 10^9 steps in total, far too slow. It also stores every number ever seen, which the problem does not need.

From brute force to the idea

  1. Find the waste. To answer "k-th largest" you never look at anything outside the top k. The sort ranks thousands of numbers that can never be the answer.
  2. Keep only the top k. Hold exactly k numbers. The k-th largest is the smallest of them.
  3. Use a min-heap. Python's heapq is a min-heap, so heap[0] is the smallest of the k kept numbers, which is the answer, readable in O(1).
  4. Push, then trim. A new number is pushed in. If the heap now holds k + 1 numbers, heappop removes the smallest, which is the one that just dropped out of the top k (possibly the new number itself).
  5. Reuse add for the start. The constructor feeds the starting numbers through the same add, so one code path does everything.

This is the key idea: a min-heap of size k whose front is the k-th largest.

The key idea

Keep a min-heap of size k; its top is the k-th largest. Each add costs O(log k).

Python solution

class KthLargest:
    def __init__(self, k, nums):
        self.k, self.heap = k, []
        for x in nums:
            self.add(x)
    def add(self, x):
        heappush(self.heap, x)
        if len(self.heap) > self.k:
            heappop(self.heap)        # weakest of the top k leaves
        return self.heap[0]           # the k-th largest so far

LeetCode adds the imports for you. To run this on your own machine, put this at the top: from heapq import heappush, heappop

In the interactive version each line lights up as the animation runs, and you can type your own input to see the algorithm handle it.

Complexity

ApproachTimeSpace
Brute forceO(m log m) per add, m = numbers stored so farO(m): every number is kept
Min-heap of size k (shown code)O(log k) per add; O(n log k) for the constructor's n starting numbersO(k): never more than k + 1 items at once

Edge cases

  • k = 1: the heap holds one number, the maximum so far. KthLargest(1, []) gives -1, -1, 5 after adds of -1, -3, 5.
  • Duplicates count separately: with k = 3 and starting numbers [4, 5, 8, 2], adding 5 gives 5, because the top three are 8, 5, 5.
  • Starting list one short of k (k = 3, [1, 2]): the first add fills the heap to k, so the answer is real. The problem guarantees at least k − 1 starting numbers.
  • Fewer than k numbers in total: the code does not complain. KthLargest(3, [5]) followed by add(5) returns 5, the smallest of two numbers, which is not a true 3rd largest. Only call it within the guarantee.
  • Negative numbers work like any others.
  • Imports: the code needs from heapq import heappush, heappop; they are not part of the shown snippet.

Common mistakes

  • Using a max-heap of everything and popping k times to peek, which costs O(k log n) per call.
  • Returning heap[-1] instead of heap[0]. The last list slot is just some leaf of the tree, not the smallest.
  • Trimming too early (>= k) so the heap holds k − 1 numbers and the answer is the (k − 1)-th largest.
  • Forgetting that the new number may be the one that leaves. That is fine, and it is why pushing first and then trimming is safe.
Your turn: k-th smallest in a stream

Same class, but add must now return the k-th smallest number seen so far. Describe your approach, then write it if you like.

Compare with our answer

Flip the roles. Keep the k smallest numbers; the k-th smallest is then the largest of them, so we need a max-heap. Python only has a min-heap, so store negated values.

from heapq import heappush, heappop

class KthSmallest:
    def __init__(self, k, nums):
        self.k, self.heap = k, []     # holds -x for the k smallest x
        for x in nums:
            self.add(x)

    def add(self, x):
        heappush(self.heap, -x)
        if len(self.heap) > self.k:
            heappop(self.heap)        # drops the largest of the k + 1
        return -self.heap[0]

With k = 2, adds of 5, 3, 4 return 5, 5, 4 once two numbers have arrived. Time O(log k) per add, space O(k).

A strong answer mentions: a max-heap of size k (negated values in Python), that the front is the k-th smallest, and why each add is O(log k).

Check what stuck

1. A stream of prices arrives and after each one you must report the 5th cheapest price so far. Which structure fits best?

2. Why does each add cost O(log k) rather than O(log n), where n is the count of all numbers seen?

3. A learner changes the last line to return self.heap[-1]. Which test still passes?

Score 60% or more and the lesson is marked complete.