Kth Largest Element in a Stream

Easy#703k largest

Build a class that gets a number k and a starting list of numbers, and then gets more numbers one at a time. After each new number it returns the k-th largest of all the numbers it has seen, repeats counted. Our example: k = 3, the list [6, 2, 9, 4, 1], then add(5), add(3), add(10) — they return 5, 5 and 6.

703 Kth Largest Element in a StreamWalkthrough · 1×

Example: k = 3, nums = [6, 2, 9, 4, 1], then add(5), add(3), add(10). Top row: the numbers in the order the class gets them; below, the min-heap.

numsadd(val)629415310min-heapk = 3add returned—
not arrived yetval, just pushedin the heaproot, popped nextpoppedk-th largest, returned

KthLargest(3, [6, 2, 9, 4, 1]) is created: init runs once

01/22
restart · back · play · step
Speed
1class KthLargest:
2 function init(k, nums):
3 heap = min-heap of nums
4 while size of heap > k:
5 pop min from heap
6 function add(val):
7 push val into heap
8 if size of heap > k:
9 pop min from heap
10 return min of heap
state
k
3
val
–
heap
–
historyclick a step to go back

← → step · space play/pause

Why it works

  1. The heap always holds the k largest numbers seen so far. The smallest of them is on top, and that is exactly the k-th largest.
  2. A number below the root cannot be among the k largest, now or later: numbers only arrive and never leave. So it goes in and is popped at once, as 3 is here.
  3. The heap never grows past k + 1, so each add costs O(log k) however many numbers came before.

Complexity

init: time O(n log n) for n numbers. Each add: time O(log k), one push and at most one pop. Memory O(k) after init: the heap keeps k numbers.

nextNow solve it yourself, no hints.

Solve on LeetCode ↗

The problem and its statement belong to LeetCode. Here are our own retelling, example and solution. Patterns Hero is not affiliated with LeetCode.