Sweaty Imposter

Kth Largest Element in a Stream

EasyTop K ElementsNeetCode 150JuniorOpen on LeetCodeUpdated

Design a class KthLargest that tracks the kth largest value in a stream of numbers. KthLargest(k, nums) starts the stream with the integers in nums. add(val) appends val to the stream and returns the kth largest value seen so far, counting duplicates. When add returns, the stream always holds at least k values.

Examples

KthLargest(2, [5,1,8]); add(3); add(9); add(6); add(10) returns 5, 8, 8, 9

The two largest values start as 8 and 5. Adding 3 changes nothing, adding 9 pushes 5 out, adding 6 is too small to matter, and adding 10 pushes 8 out.

KthLargest(1, []); add(-2); add(-5); add(4) returns -2, -2, 4

With k = 1, add returns the running maximum.

KthLargest(3, [4,4]); add(4); add(2) returns 4, 4

Duplicates count separately, so three 4s fill the top three.

Constraints

  • 1 <= k <= 10^4
  • 0 <= nums.length <= 10^4
  • -10^4 <= nums[i], val <= 10^4
  • At most 10^4 calls will be made to add.

Hints

Hint 1

You only ever care about the k largest values. What happens to a value that falls out of that group?

Hint 2
A pointer toward the approach
Hint 3
The full approach, step by step

Drill This: Your Approach First

Approach

Keep a min-heap of the k largest values seen so far. Its root is the smallest of them, which is exactly the kth largest overall. Push every new value, and whenever the heap grows past k, pop the root. Building it from nums costs O(n log k), and each add is O(log k) time with O(k) space.

Time

O(log k) per add

Space

O(k)

Pitfall

Using a max-heap of every value, or sorting on each add. The kth largest then takes k pops or a full sort every call, while a size-k min-heap answers in O(1) after an O(log k) update.

Solutions

class KthLargest {
    private final int k;
    private final PriorityQueue<Integer> heap = new PriorityQueue<>();

    public KthLargest(int k, int[] nums) {
        this.k = k;
        for (int x : nums) add(x);
    }

    public int add(int val) {
        heap.offer(val);
        if (heap.size() > k) heap.poll();
        return heap.peek();
    }
}
Drill This