086. Kth Largest Stream Class

Why this mechanism works

The root of a min-heap containing the largest k values is the kth largest value itself. Unlike the previous exercise, there is no need to sort winners because only their weakest member is queried. Constructor inputs go through the same insertion transition as later arrivals.

State and boundaries

heap contains the largest at-most-k values observed. Its root is meaningful as kth largest only when its size reaches k.

Protocol

1. Initialize an empty heap and insert initial values.
2. For add, push the new value.
3. Evict the minimum if size exceeds k.
4. Return the root if size is k, else None.

Visualization

k=3, winners [4,5,8] -> kth=4
add 3 -> keep [4,5,8] -> 4
add 5 -> keep [5,5,8] -> 5

Python implementation

import heapq
from structures import run_operations

class KthLargest:
    def __init__(self, k, values):
        if k < 1:
            raise ValueError('k must be positive')
        self.k, self.heap = k, []
        for value in values:
            self.add(value)

    def add(self, value):
        heapq.heappush(self.heap, value)
        if len(self.heap) > self.k:
            heapq.heappop(self.heap)
        return self.heap[0] if len(self.heap) == self.k else None

Worked execution

Recorded state changes after statements; L numbers refer to the solution file. Long traces are explicitly condensed.

L6 __init__: if k < 1:
self=KthLargest{}; k=3; values=[4, 5, 8, 2]

L8 __init__: self.k, self.heap = k, []
self=KthLargest{'k':3, 'heap':[]}; k=3; values=[4, 5, 8, 2]

L9 __init__: for value in values:
self=KthLargest{'k':3, 'heap':[]}; k=3; values=[4, 5, 8, 2]; value=4

L13 add: heapq.heappush(self.heap, value)
self=KthLargest{'k':3, 'heap':[...]}; value=4

L10 __init__: self.add(value)
self=KthLargest{'k':3, 'heap':[...]}; k=3; values=[4, 5, 8, 2]; value=4

L9 __init__: for value in values:
self=KthLargest{'k':3, 'heap':[...]}; k=3; values=[4, 5, 8, 2]; value=5

L13 add: heapq.heappush(self.heap, value)
self=KthLargest{'k':3, 'heap':[..., ...]}; value=5

L10 __init__: self.add(value)
self=KthLargest{'k':3, 'heap':[..., ...]}; k=3; values=[4, 5, 8, 2]; value=5

... 12 intermediate state changes omitted ...

L13 add: heapq.heappush(self.heap, value)
self=KthLargest{'k':3, 'heap':[..., ..., ..., ...]}; value=9

L15 add: heapq.heappop(self.heap)
self=KthLargest{'k':3, 'heap':[..., ..., ...]}; value=9

L13 add: heapq.heappush(self.heap, value)
self=KthLargest{'k':3, 'heap':[..., ..., ..., ...]}; value=4

L15 add: heapq.heappop(self.heap)
self=KthLargest{'k':3, 'heap':[..., ..., ...]}; value=4

L6 __init__: if k < 1:
self=KthLargest{}; k=3; values=[]

L8 __init__: self.k, self.heap = k, []
self=KthLargest{'k':3, 'heap':[]}; k=3; values=[]

L13 add: heapq.heappush(self.heap, value)
self=KthLargest{'k':3, 'heap':[...]}; value=1

L13 add: heapq.heappush(self.heap, value)
self=KthLargest{'k':3, 'heap':[..., ...]}; value=2

Why the solution is correct

The bounded winner-pool invariant follows from removing the minimum of k+1 candidates. With k retained values, exactly k-1 retained values are at least as large as the minimum, making that minimum the kth order statistic with multiplicity. Fewer values cannot define it.

Time and space

O(log(k+1)) time per add and O(k) space; constructor cost O(m log(k+1)) for m initial values.

Common mistakes

Returning a root before k observations gives the minimum-so-far rather than a defined kth largest. Duplicate values count separately.

Reasoning card

Transfer exercise

Allow deletion of old values from a sliding stream. Explain why a plain bounded heap no longer contains enough history.