Kth Largest in a Stream | Practice

Write a class KthLargest that follows a stream of integers:

KthLargest(k, nums) starts with the integer k and the values already in nums.
add(val) adds val to the stream and returns the k-th largest value seen so far, counting from 1, largest first, with equal values counted separately.

nums may hold fewer than k values, but there are always at least k values once add has added its own.

Each test is a list of calls, starting with the constructor; the expected answer lists what each call returns (null for the constructor).

Example 1

Calls: KthLargest(2, [6, 1, 3]), add(2), add(7), add(5), add(9)
Returns: [null, 3, 6, 6, 7]

Only the two largest values matter. They are 6 and 3 at first, so adding 2 returns 3; after 7 arrives they are 7 and 6; 5 changes nothing; after 9 they are 9 and 7.

Example 2

Calls: KthLargest(1, []), add(-3), add(-2), add(-4)
Returns: [null, -3, -2, -2]

With k = 1 each call returns the largest value so far.

Constraints

1 ≤ k ≤ 10⁴
nums holds 0 to 10⁴ values.
Every value is between −10⁴ and 10⁴.
A test makes at most 10⁴ calls to add.

Show the pattern

Heap

A new value only matters if it beats the current k-th largest. A min-heap of the k largest values so far keeps that cut-off on top, ready to compare with and replace.

See heap in a visualiser

Show the approach

Keep a min-heap of the k largest values seen so far. The constructor adds each value of nums the same way add does. add(val) pushes val, pops the smallest if the heap now holds k + 1 values (it can never be among the k largest again), and returns the top: the smallest of the k largest, which is the k-th largest overall.

Time: O(n log k) to start, O(log k) per add · Space: O(k)

Brush up firstHeap visualiser