Kth Largest Element in a Stream

Time — O(log k) per add: each add does a heap push/pop bounded by size k.
Space — O(k): the heap holds at most k elements.

Easy

Topics

HeapDesignBinary Search Tree

Design a class to find the kth largest element in a stream (the kth largest in sorted order, not the kth distinct). Implement KthLargest(k, nums) which initializes with an integer k and a stream of integers nums, and add(val) which appends val and returns the kth largest element so far.

Example 1

Input:  operations = ["KthLargest","add","add","add","add","add"], values = [[3,[4,5,8,2]],[3],[5],[10],[9],[4]]
Output: [null,4,5,5,8,8]

Constraints

1 <= k <= 10^4
At least k elements exist when add is queried.
At most 10^4 calls to add.

Run ⌘' · Submit ⌘⏎