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
addrule 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
- 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.
- Keep only the top k. Hold exactly k numbers. The k-th largest is the smallest of them.
- Use a min-heap. Python's
heapqis a min-heap, soheap[0]is the smallest of the k kept numbers, which is the answer, readable in O(1). - Push, then trim. A new number is pushed in. If the heap now holds k + 1 numbers,
heappopremoves the smallest, which is the one that just dropped out of the top k (possibly the new number itself). - Reuse
addfor the start. The constructor feeds the starting numbers through the sameadd, 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 farLeetCode 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
| Approach | Time | Space |
|---|---|---|
| Brute force | O(m log m) per add, m = numbers stored so far | O(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 numbers | O(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 firstaddfills 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 byadd(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 ofheap[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.
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).
1. A stream of prices arrives and after each one you must report the 5th cheapest price so far. Which structure fits best?
To keep the 5 smallest you must be able to evict the largest of them, so you need a max-heap. A min-heap of size 5 would evict the cheapest, the opposite of what you want. The other two options keep all prices and cost more per call.
2. Why does each add cost O(log k) rather than O(log n), where n is the count of all numbers seen?
Push and pop cost O(log of the heap size), and trimming keeps that size at most k + 1. Comparing only with the front would not place the number correctly, and heapq does not skip anything on its own.
3. A learner changes the last line to return self.heap[-1]. Which test still passes?
With k = 1 the heap has one item, so the last slot is also the front. With larger k the last slot is some leaf, not necessarily the smallest: the first test returns 8, 8, 8 and the second 7, 7.
Score 60% or more and the lesson is marked complete.