Kth Largest Element in a Stream

Q: Why use a min-heap and not a max-heap for the k-th largest element?

The smallest of the k largest values is both the answer and the value a newcomer has to beat, and a min-heap of size k keeps it on top. A max-heap of every value puts the largest on top, so reaching the k -th means popping k-1 values and pushing them back on every arrival.

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

Each arrival costs O(log k) : one comparison with the top and at most one sift through a heap of k values. Building the heap from nums costs O(n log k) , so the whole run is O((n + m) log k) time and O(k) extra space.

EasyHeap

+10

A stream of integers starts with the values in nums. Then the values of adds arrive one at a time. After each arrival, record the k-th largest value among everything seen so far, counting equal values separately. Return the recorded values in order, one for each value of adds.

nums holds at least k-1 values, so after the first arrival there are always at least k values to choose from.

Function

kthLargestStream(k: integer, nums: integer-array, adds: integer-array) → integer-array

kinteger: the rank to report, 1 for the largest value
numsinteger-array: the values already in the stream
addsinteger-array: the values that arrive, in order
Returnsinteger-array: the k-th largest value after each arrival

Constraints

1 ≤ nums.length ≤ 10⁴
1 ≤ adds.length ≤ 10⁴
1 ≤ k ≤ nums.length + 1
-10⁴ ≤ nums[i], adds[i] ≤ 10⁴
nums can be in any order, and equal values count as separate values.

Examples

Input: k = 3nums = [7, 1, 5]adds = [3, 9, 6, 2, 8]
Output: [3, 5, 6, 6, 7]
Explanation: After 3 arrives the third largest of 7, 5, 3 and 1 is 3. Then 9 lifts it to 5, 6 lifts it to 6, 2 changes nothing, and 8 lifts it to 7 (9, 8, 7).

Input: k = 1nums = [-2]adds = [-5, 0, -1, 4]
Output: [-2, 0, 0, 4]
Explanation: With k = 1 the answer is the largest value so far: -2 until 0 arrives, still 0 after -1, then 4.

Follow-up

How would you answer the same question if values could also be removed from the stream?

Hints

Open them one at a time. Each one gives away a little more.

0 of 3 opened

Solution

Values never leave the stream, so a value that falls below the current k-th largest is out for good. Keep only the k largest values in a min-heap: its top is the answer, and each arrival costs one comparison and at most one O(log k) heap update.

Sort after every arrival

Correct, but does not finish on the largest tests

Intuition

Keep every value in a list. After each arrival, sort it in increasing order and read index length-k, the k-th largest by definition.

Each arrival sorts up to n + m values, where n and m are the lengths of nums and adds. With 10^4 of each, that is about 2 × 10^9 comparisons in total.

Algorithm

Copy nums into a list values.
For each value of adds, append it to values.
Sort values in increasing order and record values[length-k].
Return the recorded values.

def kthLargestStream(k, nums, adds):
    values = list(nums)
    result = []
    for x in adds:
        values.append(x)
        values.sort()
        # In increasing order the k-th largest sits k places from the end.
        result.append(values[len(values) - k])
    return result

Min-heap of the k largest values

Intuition

Once a value has k larger values above it, that stays true for the rest of the stream, so only the k largest values seen so far matter. Store them in a min-heap. Its top is the smallest of the k largest, which is exactly the k-th largest overall.

When x arrives and the heap is full, compare it with the top. If x is not larger, it is not among the k largest and nothing changes. If it is larger, the top drops out: replace it with x and sift down, in O(log k). The starting values go through the same routine, so nums may be longer than k.

In the first example the heap holds 7, 1 and 5 after nums, with 1 on top. The arrival 3 replaces 1, and the top, 3, is the first answer.

Algorithm

Start with an empty min-heap.
To add x: if the heap holds fewer than k values, push x. Otherwise, if x is larger than the top, replace the top with x and restore the heap order.
Add every value of nums this way.
For each value of adds, add it and record the top of the heap.
Return the recorded values.

import heapq


def kthLargestStream(k, nums, adds):
    # A min-heap of the k largest values so far; heap[0] is the smallest of them.
    heap = []

    def add(x):
        if len(heap) < k:
            heapq.heappush(heap, x)
        elif x > heap[0]:
            heapq.heapreplace(heap, x)  # drop the top, add x

    for x in nums:
        add(x)
    result = []
    for x in adds:
        add(x)
        result.append(heap[0])  # the k-th largest so far
    return result

Pitfalls and edge cases

Dropping duplicates. The four largest of 9, 6, 6, 6, 2 are 9, 6, 6 and 6. A set, or a check that skips values already present, returns 2 on the third example instead of 6.
Reading the answer before adding. When nums holds k-1 values the heap is full only after the first arrival, so add first, then read the top.
Counting from the wrong end after a sort. In increasing order the k-th largest is at index length-k; index k-1 holds the k-th smallest.
Taking the default heap order. C++'s priority_queue and Rust's BinaryHeap are max-heaps: pass greater<int> or wrap values in Reverse.

Frequently asked questions3

Why use a min-heap and not a max-heap for the k-th largest element?

The smallest of the k largest values is both the answer and the value a newcomer has to beat, and a min-heap of size k keeps it on top. A max-heap of every value puts the largest on top, so reaching the k-th means popping k-1 values and pushing them back on every arrival.

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

Each arrival costs O(log k): one comparison with the top and at most one sift through a heap of k values. Building the heap from nums costs O(n log k), so the whole run is O((n + m) log k) time and O(k) extra space.

Can Kth Largest Element in a Stream be solved with a sorted list?

Yes. Keep all values sorted, insert each arrival at its place with binary search, and read the value k places from the end. The search is O(log n), but shifting the values after the insert point is O(n) per arrival: about 1.5 × 10^8 shifts for 10^4 starting values and 10^4 arrivals.

def kthLargestStream(k, nums, adds):
    # Write code here

Test #1

Test #2

Test #3

Arguments

k = 3
nums = [7, 1, 5]
adds = [3, 9, 6, 2, 8]

Expected Output

[3, 5, 6, 6, 7]