Find Kth Largest in Stream
Description
Design a class to find the kth largest element in a stream of numbers. Implement methods to initialize with k and a list of numbers, and to add a new number while returning the current kth largest.
Examples
k = 3, nums = [4,5,8,2], stream = [[3],[5],[10]][4,5,5]Initial array sorted: [2,3,4,5,8]. After add(3): sorted [2,3,3,4,5,8], 3rd largest is 4. After add(5): sorted [2,3,3,4,5,5,8], 3rd largest is 5. After add(10): sorted [2,3,3,4,5,5,8,10], 3rd largest is 5.
k = 3, nums = [4,5,8,2], stream = [[1]][4]After adding 1 to [4,5,8,2], the sorted array is [1,2,4,5,8]. The 3rd largest element is 4.
k = 2, nums = [1], stream = [[7],[3],[9],[2]][1,3,7,7]Starting with nums=[1] and k=2. After adding 7: [1,7] → 2nd largest is 1. After adding 3: [1,3,7] → 2nd largest is 3. After adding 9: [1,3,7,9] → 2nd largest is 7. After adding 2: [1,2,3,7,9] → 2nd largest is still 7.
Constraints
- •
1 ≤ k ≤ 10⁴
Ready to solve this problem?
Practice solo and sharpen your skills for technical interviews.