Start practising

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, 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.

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 Java code.

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].
Java
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.
Java
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.

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.