Kth Largest Element in a Stream

Easy~20 min

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", "add", "add", "add", "add", "add"] [[3, [4, 5, 8, 2]], [3], [5], [10], [9], [4]]
Output: [null, 4, 5, 5, 8, 8]
Explanation: KthLargest kthLargest = new KthLargest(3, [4, 5, 8, 2]); kthLargest.add(3); // return 4 (stream: [2,3,4,5,8], 3rd largest = 4) kthLargest.add(5); // return 5 (stream: [2,3,4,5,5,8], 3rd largest = 5) kthLargest.add(10); // return 5 (stream: [2,3,4,5,5,8,10], 3rd largest = 5... wait) Actually: after init [2,4,5,8], heap keeps top 3: [4,5,8] add(3): 3 < 4 (heap top), skip → return 4 add(5): 5 >= 4, push → [4,5,5,8] → pop min → [5,5,8] → return 5 add(10): push → [5,5,8,10] → pop min → [5,8,10] → return 5 add(9): push → [5,8,9,10] → pop min → [8,9,10] → return 8 add(4): 4 < 8, skip → return 8

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 time complexity: O(log k) per add
Code
Ctrl+EnterRun|Ctrl+⇧+EnterSubmit
Output

Run your code to see results

Use Cmd+Enter to run