How do you approach Kth Largest Element in a Stream?

Re-sorting after every add is O(n log n) per call - too slow for a stream.

What is the time complexity of Kth Largest Element in a Stream?

Time complexity: O(log k) per add; O(n log k) to seed.. Space complexity: O(k).

What are common mistakes on Kth Largest Element in a Stream?

Using a max-heap for a k-largest question. The size-k min-heap is what turns O(n log n) into O(n log k). An inverted comparator, which is silent: the code runs and returns confidently wrong answers. Re-heapifying inside the loop instead of once up front.

gitGood.dev

← Back to problems

Kth Largest Element in a Stream

EasyData Structures

Description

Design a structure that reports the kth largest value seen so far in a stream of numbers (the kth largest in sorted order, not the kth distinct value).

Implement kthLargest(k, nums, adds) where nums seeds the stream and adds is a list of values added one at a time. Return a list containing the kth largest value after each add.

You may assume there are always at least k values when a result is requested.

Example 1

Input: k = 3, nums = [4,5,8,2], adds = [3,5,10,9,4]

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

Example 2

Input: k = 1, nums = [], adds = [-1,1,-2,-4,3]

Output: [-1, 1, 1, 1, 3]

Example 3

Input: k = 2, nums = [0], adds = [-1,3,5,10,9,4]

Output: [-1, 0, 3, 5, 9, 9]

Constraints

- 1 <= k <= 10^4 - 0 <= nums.length <= 10^4 - -10^4 <= values <= 10^4 - At most 10^4 adds; there are always at least k elements when a result is produced.

Kth Largest Element in a Stream: approach, complexity and pitfalls

An easy heap / priority queue problem, graded against 6 test cases (3 of them hidden).

The pattern: Heap / Priority Queue

A priority queue for "top k" and streaming-median questions.

Reach for it when you see: "Top/smallest k", a running median, or repeatedly needing the current minimum.

More Heap / Priority Queue problems →

If you are stuck

Show the 3-step hint ladder

Re-sorting after every add is O(n log n) per call - too slow for a stream.
Keep a MIN-heap holding only the k largest values seen. Its smallest element is the kth largest overall.
On each add, push, and if the heap exceeds size k, pop the smallest. The answer is always the heap's root.

The optimal approach

Show the approach: A min-heap of size k, which is the counterintuitive part

The instinct for "kth largest" is a max-heap, and that is the wrong structure. You do not need every value ordered - only the boundary between the top k and everything else. A min-heap capped at size k holds exactly the k largest values seen, and its root is the smallest of those: the kth largest overall.

Each add is a push followed by a pop when the size exceeds k, both O(log k), and the answer is always available at the root in O(1). Values that fall out of the top k are discarded permanently, which is what keeps memory at O(k) rather than O(n) - the property that matters for an unbounded stream.

Compare the alternatives: re-sorting is O(n log n) per add, and a max-heap of everything answers a query in O(k log n) since you must pop k times and push them back. The size-k min-heap beats both, and generalizes directly to "top k frequent" and "k closest points".

Note the values are not deduplicated - the kth largest in sorted order counts repeats, which is why a stream of identical values returns that value.

Time: O(log k) per add; O(n log k) to seed.
Space: O(k)

The full reference solution in every supported language stays in the editor above - reveal it there once you have had a real attempt.

What the tests check

Read off this problem's own test suite, so these are the cases a submission actually has to survive.

Empty input. At least one case passes an empty collection. Make sure your loop bounds and any "first element" read survive a length of zero.
Single element. A one-element case is included. Two-pointer and window solutions frequently return the wrong thing when the two indices start out equal.
Duplicate values. Repeated values appear in the input, so any logic that assumes distinct elements - or that skips over equal neighbours - is exercised.
Negative numbers. The suite includes negative values. Running-sum, min/max seeding and any "initialise to zero" step need to handle them.

Common Heap / Priority Queue mistakes

These apply to the pattern as a whole, not just this problem.

Using a max-heap for a k-largest question. The size-k min-heap is what turns O(n log n) into O(n log k).
An inverted comparator, which is silent: the code runs and returns confidently wrong answers.
Re-heapifying inside the loop instead of once up front.