Kth Largest Element in a Stream

Problem

Design a class KthLargest that tracks the kth largest element in a stream of numbers (note: the kth largest value in sorted order, counting duplicates — not the kth distinct value).

• The constructor takes k and an initial array nums.
• add(val) appends val to the stream and returns the kth largest element seen so far.

Examples

Constraints

1 ≤ k ≤ 10⁴, up to 10⁴ add calls, values in ±10⁴.

Attempt it first

The naive version is easy; the point is to find the version whose add does not re-sort the whole stream each time. Before reading on, ask yourself the sharp question: to answer "kth largest," how much of the stream do you actually need to keep? You are never asked about the elements smaller than the kth largest — can you throw them away? And of the elements you keep, which single one is the answer, and where would it sit in a heap so you can read it in O(1)?