Implement k-th largest in a number stream

You are designing a small library to monitor statistics over a stream of integers.

Implement a data structure that, given an integer k and an initial list of integers, supports the following operation:

• add(val): insert the integer val into the stream and return the k-th largest element among all elements seen so far (including the new one).

More formally, after each call to add, if you took all numbers that have been provided (both the initial list and all numbers added so far), sorted them in non-decreasing order, you should return the element that is k positions from the end (the k-th largest). You may assume that k is always valid (i.e., there are at least k elements after each add call).

API to implement

Define a class or type with:

• A constructor that takes:

  • k (an integer)
  • nums (a list/array of integers, possibly empty)

• A method:

  • add(val: int) -> int that inserts val and returns the current k-th largest element.

Constraints

• You may assume:
  • 1 \le k \le 10^4
  • At most 10^4 calls to add will be made.
  • Each integer value fits in a standard 32-bit signed integer.
• Your design should be efficient enough to handle the worst-case number of add calls within typical interview time complexity expectations.

Describe only the code-level behavior and interface; you do not need to provide a working implementation here.

K-th Largest Element in a Number Stream

You are designing a small library to monitor statistics over a stream of integers.

Implement a data structure that, given an integer k and an initial list of integers, supports inserting new values and querying the k-th largest element seen so far.

Because the online grader calls a single function, you implement the stateful design as solution(k, nums, operations):

• k: the rank to track (1-indexed from the largest).
• nums: the initial list of integers already in the stream (possibly empty).
• operations: a list of integers, where each value represents one add(val) call in order.

For every value in operations, insert it into the stream and record the current k-th largest element among all numbers seen so far (the initial nums plus every value added up to and including this one). "k-th largest" means: sort all elements in non-decreasing order and take the element k positions from the end. Return the list of these recorded values, one per add call.

You may assume k is always valid (there are at least k elements after each add).

Constraints

• 1 <= k <= 10^4
• At most 10^4 add calls (length of operations).
• Each integer fits in a signed 32-bit integer.
• Aim for O(log k) per add (a size-k min-heap keeps the top-k largest; its root is the k-th largest).

Examples

Example 1

Input: (3, [4, 5, 8, 2], [3, 5, 10, 9, 4])
Output: [4, 5, 5, 8, 8]

Explanation: Start with [4,5,8,2], k=3. add(3): pool {2,3,4,5,8}, 3rd largest=4. add(5): 3rd largest=5. add(10): 3rd largest=5. add(9): pool now has 8,9,10 as top three, 3rd largest=8. add(4): 3rd largest still 8.

Example 2

Input: (1, [], [5, 3, 8, 1, 10])
Output: [5, 5, 8, 8, 10]

Explanation: Empty start, k=1 tracks the running maximum: 5, then 5, then 8, then 8, then 10.

Hints

1. You never need every element sorted at once. To know the k-th largest, you only need to remember the k largest values seen so far.
2. A min-heap capped at size k does exactly that: push each new value, and if the heap grows past k, pop the smallest. The root is then the k-th largest.
3. Initialize by heapifying nums and trimming it down to k elements before processing any add call.
4. Each add is O(log k): one push plus at most one pop. With at most 10^4 adds this is comfortably fast.