EasyTreeDesignBinary Search TreeHeap (Priority Queue)Data StreamBinary Tree

Kth Largest Element in a Stream

1 approach, code in every language

Design a class that tracks the `k`-th largest element within a stream of integers. Note this is the `k`-th largest in sorted order, not the `k`-th distinct value.

Implement the class:

- `KthLargest(k, nums)` initializes the object with the integer `k` and an initial list of integers `nums`. - `add(val)` appends `val` to the stream and returns the element that is currently the `k`-th largest.

It is guaranteed that there will be at least `k` elements in the stream when `add` is called.

Example 1

Input: ["KthLargest","add","add","add","add","add"] [[3,[4,5,8,2]],[3],[5],[10],[9],[4]]

Output: [null, 4, 5, 5, 8, 8]

Seeded with k = 3 and [4,5,8,2] the 3rd largest is 4. add(3) -> 4, add(5) -> 5, add(10) -> 5, add(9) -> 8, add(4) -> 8.

Example 2

Input: ["KthLargest","add","add"] [[1,[]],[-1],[5]]

Output: [null, -1, 5]

With k = 1 the answer is simply the maximum seen so far. After adding -1 the largest is -1; after adding 5 the largest is 5.

Constraints

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

Size-k min-heap

Hold the k largest values seen so far in a min-heap; the root is always the kth largest.

Loading animation…

Intuition

Just like finding the kth largest of a static array, the kth largest in a stream is the smallest element among the k largest seen so far. A min-heap capped at size k keeps exactly those k values with their minimum at the root, which is the answer we return after every insertion. Seeding the heap from the initial list applies the same trim-to-k rule, so the structure is consistent from the start. Every subsequent add pushes the new value and, if the heap overflows, pops the smallest — an O(log k) operation. Reading the answer is then just peeking at the root.

Algorithm walkthrough

1In the constructor, create an empty min-heap and insert every value from the initial nums, trimming to size k as you go.
2Trimming means: whenever the heap grows past k elements, pop the root so only the k largest survive.
3For add(val), push val onto the heap.
4If the heap now exceeds size k, pop the smallest element to keep only the k largest.
5The root of the heap is the smallest of the k largest values, i.e. the current kth largest.
6Return that root.

Implementation

import heapq
from typing import List

class KthLargest:
    def __init__(self, k: int, nums: List[int]):
        self.k = k
        self.heap = nums[:]
        heapq.heapify(self.heap)
        while len(self.heap) > k:
            heapq.heappop(self.heap)

    def add(self, val: int) -> int:
        heapq.heappush(self.heap, val)
        if len(self.heap) > self.k:
            heapq.heappop(self.heap)
        return self.heap[0]

Time

O(log k) per add; O(m log k) to build from m initial values

Space

O(k)

The heap never exceeds k+1 elements, so memory is bounded by k regardless of stream length.

Create a free account to see the solution

You get the step-by-step animation, the intuition and clean code in every language. Free, no credit card.

Create a free account Already have an account? Sign in

Back to Priority Queues

After the pattern

Now solve one you haven't seen.

Reading a pattern isn't the same as using it. The practice set has 1,194 original problems on the same techniques, each graded in your browser.

Open the practice set Start the FDE path

1,194 problems · 15,062 graded tests · free