Kth Largest Element in a Stream

Easy Heaps Top K / Kth Largest / Smallest Original on LeetCode

Kth Largest Element in a Stream is a easy heaps problem solved with the top k / kth largest / smallest pattern. The best approach, optimal (min-heap of size k), runs in O(log k) per add time and O(k) space. Below are 2 approaches in Java, Python, C++ and JavaScript, from sorted list up.

Problem

Design a class that receives a stream of numbers and, after each new number, returns the k-th largest number seen so far.

Examples

Example 1

Input
KthLargest(3, [4, 5, 8, 2]); add(3); add(5); add(10); add(9); add(4)
Output
4, 5, 5, 8, 8

Constraints

  • 1 <= k <= 10^4; up to 10^4 calls to add.
  • There are at least k elements whenever you query.

Solve it here

Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.

00:00
Testcase

Run checks the testcases above (1 examples, or your own). Submit also runs 9 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.

Animated walkthrough

A narrated, step-by-step animation that builds the solution from the idea up. Press play, or step through it at your own pace.

Concepts first, then the problem and every approach, step by step.

Space to play or pause · ← → to jump a step · click or drag the bar to seek

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.

ApproachTimeSpace
Sorted listO(n) per addO(n)
Optimal (min-heap of size k)O(log k) per addO(k)

1Sorted list

TimeO(n) per addInserting into an array list shifts elements.
SpaceO(n)

Keep all values in a sorted list (binary search insert) and read index size - k.

  1. Insert at bisect position; return list[size - k].
class KthLargest {
    private final List<Integer> vals = new ArrayList<>();
    private final int k;

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

    public int add(int val) {
        insert(val);
        return vals.get(vals.size() - k);
    }

    private void insert(int x) {
        int i = Collections.binarySearch(vals, x);
        vals.add(i < 0 ? -i - 1 : i, x);
    }
}

2Optimal (min-heap of size k)

TimeO(log k) per add
SpaceO(k)

Keep a min-heap of the k largest values. On add, push; if the heap grows past k, pop the smallest. The top is the k-th largest.

  1. Constructor: add each initial value.
  2. add: offer; if size > k, poll; return peek.
class KthLargest {
    private final PriorityQueue<Integer> heap = new PriorityQueue<>();
    private final int k;

    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();
    }
}

Edge cases to test

  • The initial array has fewer than k elements
  • A new value smaller than the current k-th largest

Hints

Hint 1

A min-heap of size k keeps exactly the k largest values, with the answer on top.

FAQ

What is the best time complexity for Kth Largest Element in a Stream?

Optimal (min-heap of size k) runs in O(log k) per add time and O(k) extra space.

Which pattern does Kth Largest Element in a Stream use?

It is a heaps problem that uses the top k / kth largest / smallest pattern. Other problems with the same pattern: Kth Largest Element in an Array, Top K Frequent Words, K Closest Points to Origin.

Is there a brute force solution for Kth Largest Element in a Stream?

Yes. Sorted list takes O(n) per add time and O(n) space. Keep all values in a sorted list (binary search insert) and read index size - k.

Which edge cases should I test for Kth Largest Element in a Stream?

The initial array has fewer than k elements; A new value smaller than the current k-th largest.