Kth Largest Element in a Stream
Solve and submit on LeetCode to build your LeetCode profile. Use the hints here when you need guidance.
Problem
Design a class that is built from k and an initial list of numbers. Each call to add(val) inserts a new number and returns the kth largest value seen so far (counting duplicates).
Examples
Constraints
- • 1 <= k <= 10^4
- • 0 <= nums.length <= 10^4
- • At least k values exist whenever the kth largest is requested
Hints & approach
Hint 1
You never need values smaller than the current kth largest.
Hint 2
Keep only the k largest values seen so far.
Hint 3
A min-heap of size k keeps the kth largest right at the top.
Approachtry the hints first
Maintain a min-heap that holds at most k elements. Push every initial number, popping whenever the size exceeds k. For add, push the value and pop if the size is now k + 1. The heap then contains exactly the k largest values, and its minimum, at the root, is the kth largest overall.
Time O(log k) per add · Space O(k)
