Pattern this teaches:Heap and Top K
Kth Largest Element in a Stream
An easy Heap interview guide. Task statement, worked examples, intuition, and step-by-step solutions.
- Topic
- Heap
- Sheets
- 2
- Core for
- 10 roles
The problem
Design a class to find the kth largest element in a data stream. The kth largest element is the kth position in sorted order (not the kth distinct element). The class should accept k and an initial array of numbers, and support adding new values to the stream while efficiently returning the current kth largest element.
Example 1
- Input
- k = 3, nums = [4,5,8,2], add(3) -> 4, add(5) -> 5, add(10) -> 5, add(9) -> 8, add(4) -> 8
- Output
- [4, 5, 5, 8, 8]
- Why
- After adding 3, the stream sorted is [8,5,4,3,2] and the 3rd largest is 4. After adding 5, stream is [8,5,5,4,3,2] and 3rd largest is 5. After adding 10, stream is [10,8,5,5,4,3,2] and 3rd largest is 5. After adding 9, stream is [10,9,8,5,5,4,3,2] and 3rd largest is 8. After adding 4, 3rd largest remains 8.
Example 2
- Input
- k = 1, nums = [], add(3) -> 3, add(5) -> 5
- Output
- [3, 5]
- Why
- With k=1, we always return the maximum element. After adding 3, the max is 3. After adding 5, the max becomes 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 will be made to add.
How to think about it
Updated 2026-09-29The stream can grow forever, but curiosity is permanently capped at rank k. Any number smaller than the kth largest cannot displace it and cannot help later either. Keeping only the k largest candidates turns the query into reading the smallest among the survivors, which is exactly the job of a min-heap.
Approaches, worst first
Sort the whole list each call
time O(m * n log n) · space O(n)
Append the incoming integer to an internal buffer, sort everything descending, and read the element at index k - 1. Dead simple, but reorders the entire history on every single call even though only one rank matters.
Bounded min-heap of size kWrite this one
time O(m log k) · space O(k)
Maintain a min-heap capped at k elements. Push the new value; if the heap grows beyond k, evict the minimum. The root always holds the smallest of the top k numbers, which is by definition the kth largest overall.
Where people lose marks · 3
- Reaching for a max-heap because the problem asks for the largest. A max-heap would have to hold all stream elements and peel off k items per query, ruining the cost.
- The initial array can have fewer than k elements, even zero, as shown in the examples. Do not assume the heap is fully primed before the first add call arrives.
- Evicting before pushing when the heap is full: if the incoming value is smaller than the root, evicting the root replaces a valid top-k candidate with junk. Always push first or check the root first.
The theory behind it
Heap — the ground this problem stands on. All Heap problems
What Heap is
A heap is a specialized tree that keeps only the single most extreme item at the very top. In a min-heap, every parent node is smaller than its children, so the smallest element in the entire collection sits immediately at the root. Unlike a binary search tree, a heap does not keep all items in full sorted order. It maintains only a partial order, making it fast at giving you the single smallest or largest item without spending time sorting everything else.
When to reach for it
Reach for a heap when a problem asks for the top k largest elements, the kth smallest value, or a running median from a stream of numbers. Signals include phrases like continuously finding the cheapest item, merging k sorted linked lists, or scheduling tasks with priorities. Whenever you need repeated access to the minimum or maximum value while items are added and removed dynamically, a priority heap is the tool.
How the pattern works
To find the k largest elements, keep a min-heap of fixed size k. Push incoming numbers into the heap; whenever the heap size grows past k, pop the top item, which is the smallest among them. After processing all elements, only the k largest remain. For a running median, balance two heaps: a max-heap holding the smaller half of numbers and a min-heap holding the larger half. In code, heaps are stored compactly as flat arrays where a node at index i has children at indices 2i plus 1 and 2i plus 2.
More Heap problems
Target Roles
Core requirement for 10 roles:
Track in your role's order
Pick your target role and all 370 problems resequence to what that interview actually asks.
Start freeProblem set and role mapping as of .