Design a class KthLargest that tracks the kth largest value in a growing stream of numbers. The constructor KthLargest(k, nums) receives k and the initial numbers. Each call to add(val) inserts val and returns the current kth largest value of everything seen so far.
- 1 <= k <= 10^4
- 0 <= nums.length <= 10^4
- -10^4 <= nums[i], val <= 10^4
- When add is called there are at least k values in total
Give it a real try first. Even 15 minutes of struggle makes the solution stick far better.
Intuition
Sorting after every add costs O(n log n) per call. A value that is already below the kth largest will never matter again, because the stream only grows. So we keep only the k largest values in a min-heap. Its smallest element, the top, is the kth largest overall. Each add pushes the value and pops the top if the heap now holds more than k items.
Algorithm
- In the constructor, store
kand add every initial number. - In
add(val), pushvalinto the min-heap. - If the heap size exceeds
k, pop the smallest value. - Return the top of the heap.
O(log k) per add, O(n log k) to buildSpace: O(k)nums can be shorter than k (even empty), so do not assume the heap is full in the constructor. Trimming only when the size exceeds k handles that.class KthLargest: def __init__(self, k: int, nums: List[int]): self.k = k self.heap = [] # min-heap of the k largest values for x in nums: self.add(x)Β def add(self, val: int) -> int: heapq.heappush(self.heap, val) if len(self.heap) > self.k: heapq.heappop(self.heap) # drop values below the kth largest return self.heap[0]