Skip to main content

Kth Largest Element In A Stream

Question​

Find the k-th largest elements (sorted order) in an initial array over a stream array.

Each value in the stream array is appended to the initial array and the k-th largest element is found in the initial array.

The k-th largest elements found in this process will be returned as a result.

==========================================================================

Example 1
Input:
(k = 2, arr_initial = [4, 6], arr_stream = [5, 2, 20])

Output:
[5, 5, 6]
Constraints

1 <= k <= 10^4

1 <= len(arr_initial) <= 10^4

1 <= len(arr_stream) <= 10^4

TC

O(log(k) * (|arr_initial| + |arr_stream|))

To maintain a heap of size K = O(log(K)).

SC

O(|arr_initial| + |arr_stream| + k)

note

heapq.heappush(heap, item): Storge the item in ascending order.

Solution​

heap/Kth Largest Element in a Stream.py
import heapq


def solution(k, arr_initial, arr_stream):
    h = []

    for i in arr_initial:
        heapq.heappush(h, -1*i)
        #print(h)

    ret = []
    for val in arr_stream:
        heapq.heappush(h, -1*val)

        temp_h = h.copy()
        #print(temp_h)

        largest = None

        for i in range(k):
            largest = heapq.heappop(temp_h)

        ret.append(-1 * largest)
        #print(ret)

    return ret


result = solution(2, [4, 6], [5, 2, 20])

#print(result)
Steph
1[-4]
2[-6, -4]
Steptemp_h
1[-6, -4, -5]
2[-6, -4, -5, -2]
3[-20, -6, -5, -2, -4]
Stepret
1[5]
2[5, 5]
3[5, 5, 6]
result
[5, 5, 6]