084. Largest K Values from a Stream

Why this mechanism works

The weakest retained winner is the smallest of the current largest k, so a min-heap exposes precisely the value that should be evicted when capacity is exceeded. The heap itself is not sorted output; order the retained winners only at the end.

State and boundaries

heap contains the largest at-most-k values from the consumed stream; its root is the smallest retained winner.

Protocol

1. Return [] for nonpositive k.
2. Push each incoming value.
3. If size exceeds k, remove the minimum.
4. Sort the retained heap descending at the end.

Visualization

k=3, retained min-heap [4,5,8]
incoming 2 -> evict 2
incoming 10 -> evict 4
retained winners 5,8,10

Python implementation

import heapq

def largest_k(values, k):
    if k <= 0:
        return []
    heap = []
    for value in values:
        heapq.heappush(heap, value)
        if len(heap) > k:
            heapq.heappop(heap)
    return sorted(heap, reverse=True)

Worked execution

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

L4 largest_k: if k <= 0:
values=[4, 5, 8, 2, 10]; k=3

L6 largest_k: heap = []
values=[4, 5, 8, 2, 10]; k=3; heap=[]

L7 largest_k: for value in values:
values=[4, 5, 8, 2, 10]; k=3; heap=[]; value=4

L8 largest_k: heapq.heappush(heap, value)
values=[4, 5, 8, 2, 10]; k=3; heap=[4]; value=4

L7 largest_k: for value in values:
values=[4, 5, 8, 2, 10]; k=3; heap=[4]; value=5

L8 largest_k: heapq.heappush(heap, value)
values=[4, 5, 8, 2, 10]; k=3; heap=[4, 5]; value=5

L7 largest_k: for value in values:
values=[4, 5, 8, 2, 10]; k=3; heap=[4, 5]; value=8

L8 largest_k: heapq.heappush(heap, value)
values=[4, 5, 8, 2, 10]; k=3; heap=[4, 5, 8]; value=8

... 2 intermediate state changes omitted ...

L10 largest_k: heapq.heappop(heap)
values=[4, 5, 8, 2, 10]; k=3; heap=[4, 5, 8]; value=2

L7 largest_k: for value in values:
values=[4, 5, 8, 2, 10]; k=3; heap=[4, 5, 8]; value=10

L8 largest_k: heapq.heappush(heap, value)
values=[4, 5, 8, 2, 10]; k=3; heap=[4, 5, 8, 10]; value=10

L10 largest_k: heapq.heappop(heap)
values=[4, 5, 8, 2, 10]; k=3; heap=[5, 10, 8]; value=10

L4 largest_k: if k <= 0:
values=[2, 2, 1]; k=2

L6 largest_k: heap = []
values=[2, 2, 1]; k=2; heap=[]

L7 largest_k: for value in values:
values=[2, 2, 1]; k=2; heap=[]; value=2

L8 largest_k: heapq.heappush(heap, value)
values=[2, 2, 1]; k=2; heap=[2]; value=2

L8 largest_k: heapq.heappush(heap, value)
values=[2, 2, 1]; k=2; heap=[2, 2]; value=2

L7 largest_k: for value in values:
values=[2, 2, 1]; k=2; heap=[2, 2]; value=1

L8 largest_k: heapq.heappush(heap, value)
values=[2, 2, 1]; k=2; heap=[1, 2, 2]; value=1

L10 largest_k: heapq.heappop(heap)
values=[2, 2, 1]; k=2; heap=[2, 2]; value=1

Why the solution is correct

Adding one value temporarily creates the old winners plus the new candidate. Removing their minimum leaves the largest k of that set. Discarded older losers cannot reenter the largest k without new values improving their rank, so this maintains the correct winner pool.

Time and space

O(n log(k+1)+k log k) time and O(k) working space; returned size is at most min(k,n).

Common mistakes

Using a max-heap exposes the strongest winner rather than the eviction candidate. Deduplicating would change the multiplicity contract.

Reasoning card

Transfer exercise

Return the kth largest value after every insertion once enough values exist, without sorting the heap.