Kth Largest Element in a Stream

Kth Largest Element in a Stream

Design a class to find the kth largest element in a stream. Note that it is the kth largest element in sorted order, not the kth distinct element.

Implement the KthLargest class:

• KthLargest(k, nums): Initializes the object with the integer k and the stream of integers nums.
• add(val): Appends the integer val to the stream and returns the element representing the kth largest element in the stream.

Examples

Example 1:

Input:
  KthLargest(3, [4, 5, 8, 2])
  add(3)  -> 4
  add(5)  -> 5
  add(10) -> 5
  add(9)  -> 8
  add(4)  -> 8

Explanation:
  After init: sorted desc = [8, 5, 4, 2], 3rd largest = 4
  add(3): [8, 5, 4, 3, 2], 3rd largest = 4
  add(5): [8, 5, 5, 4, 3, 2], 3rd largest = 5
  add(10): [10, 8, 5, 5, 4, 3, 2], 3rd largest = 5
  add(9): [10, 9, 8, 5, 5, 4, 3, 2], 3rd largest = 8
  add(4): [10, 9, 8, 5, 5, 4, 4, 3, 2], 3rd largest = 8

Example 2:

Input:
  KthLargest(1, [])
  add(3)  -> 3
  add(5)  -> 5
  add(10) -> 10
  add(9)  -> 10
  add(4)  -> 10

Constraints

• 1 <= k <= 10^4
• 0 <= nums.length <= 10^4
• -10^4 <= nums[i] <= 10^4
• -10^4 <= val <= 10^4
• At most 10^4 calls will be made to add.
• It is guaranteed that there will be at least k elements in the array when you search for the kth element.

Expected Complexity

• Time: O(n log k) for initialization, O(log k) per add call
• Space: O(k)