Command Palette

Search for a command to run...

Hectal
Problem 18.3 · Heaps and Priority QueuesEasy

Kth Largest Element in a Stream

PatternTop K with a HeapCombine Structures to Design

What it teaches: Top-K as a long-lived data structure: the min-heap's top is always the k-th largest.

Practise it on judges as “Kth Largest Element in a Stream”.

The problem

Design KthLargest(int k, int[] nums) with add(int val) that adds a score and returns the k-th largest score seen so far.

Example 1

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

Constraints

  • 1 ≤ k ≤ 10⁴
  • At least k values exist whenever add returns

Pattern clues in the wording

  • → Stream
  • → k-th largest after each insert

These clues point to Top K with a Heap: Keep a heap of size k: a min-heap for the k largest, a max-heap for the k smallest.

Stuck? Take one hint at a time

KthLargest.java · starter
import java.util.*;

class KthLargest {
    public KthLargest(int k, int[] nums) {}
    public int add(int val) { return 0; }
}

Write your solution locally or in your editor for now. The in-browser runner (Java first, then Python, C++ and more) will run these tests right here.

Test cases

#InputExpected
1
ops = ["KthLargest","add","add","add","add","add"]
args = [[3,[4,5,8,2]],[3],[5],[10],[9],[4]]
[null,4,5,5,8,8]

+ 1 hidden test the code runner will check

From slow to fast

Approaches

1. Min-heap of size k · O(log k) per add
1

Min-heap of size k

Time O(log k) per add Space O(k)

Offer each value; if the heap exceeds k, poll. peek() is the k-th largest.

Approach 1
import java.util.PriorityQueue;

class KthLargest {
    private final PriorityQueue<Integer> pq = 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) {
        pq.offer(val);
        if (pq.size() > k) pq.poll();
        return pq.peek();
    }
}

Verdict: The top-K pattern exactly.

Before you submit

Edge cases and common mistakes

Test these inputs

  • Fewer than k initial values
  • Duplicates

Mistakes people make

  • Sorting a list on every add (O(n log n) per call).

Interview

Follow-up questions

What if values can also be removed?