Coding interview problems › Heaps & Top-K

🔺 Heaps & Top-K Easy

Kth Largest Element in a Stream

Kth Largest Element in a Stream: keep a min-heap of the k largest values so its root is always the answer, O(log k) per add. Tested Python, live visual.

Also searched as: kth largest in a stream using min heap · running kth largest · heapq kth largest

🔺

Try it live Free

Binary Heap & Priority Queue

Push values into the heap lab and pop the minimum: watch each one travel a single root-to-leaf path, which is why every add here costs only O(log k).

Open the playground →

The problem

Design a class that is created with an integer k and an initial list of numbers. Each call to add(val) inserts a new number and returns the k-th largest value seen so far. You may assume at least k numbers exist whenever an answer is requested.

Inputk = 3, nums = [4, 5, 8, 2]; add(3), add(5), add(10), add(9), add(4)
Output4, 5, 5, 8, 8

The key insight

You only ever care about the top k values. Keep exactly those in a min-heap: its root is the smallest of the top k, which is the k-th largest overall. A new value smaller than the root can never matter; a larger one replaces the root.

Brute force first: Appending to a list and sorting on every add costs O(n log n) per call and keeps growing.

Step-by-step approach

  1. Store k and build a min-heap from the initial numbers.
  2. Pop from the heap until it holds at most k values.
  3. On add(val), push val; if the heap now has more than k values, pop the smallest.
  4. Return the heap root heap[0].

Python solution

PYTHON 3tested
import heapq


class KthLargest:
    def __init__(self, k, nums):
        self.k = k
        self.heap = list(nums)
        heapq.heapify(self.heap)            # min-heap
        while len(self.heap) > k:
            heapq.heappop(self.heap)        # keep only the k largest

    def add(self, val):
        heapq.heappush(self.heap, val)
        if len(self.heap) > self.k:
            heapq.heappop(self.heap)        # drop the smallest
        return self.heap[0]                 # k-th largest so far

Complexity

TimeO(log k) per add
SpaceO(k)

The heap never holds more than k + 1 values, so each push and pop costs O(log k). Building it initially is O(n) for heapify plus O((n - k) log n) for the trimming pops.

Common mistakes

Frequently asked questions

What is the time and space complexity?

Each add is O(log k) and the structure uses O(k) space.

Why a min-heap and not a max-heap?

With a min-heap of the top k, the k-th largest is the minimum, available at the root in O(1). A max-heap would hold the answer deep inside the tree.

How do I make heapq behave like a max-heap?

Push negated values and negate them again when you read them. Python's heapq only provides a min-heap.

What if values can also be removed from the stream?

A plain heap cannot delete arbitrary values efficiently. Use a balanced sorted structure, such as SortedList from the sortedcontainers package, or lazy deletion with a counter.

Preparing for placements?

Take the 2-minute readiness check to find your weak patterns, then follow the placement path from DSA core to system design.

📋 2-minute readiness check The full placement path

All coding interview problems More Heaps & Top-K Binary Heap & Priority Queue lab Placement prep guides

Problem statements on this site are written in our own words. Problem names are the common names used across interview-prep communities; BitBootcamp is an independent learning platform and is not affiliated with LeetCode or any company that asks these questions.