Merge Sorted Streams

01 · Question

Given m ascending integer arrays, return all their values in ascending order, preserving duplicates. Empty arrays and an empty collection are allowed.

Example: [[1,4], [], [1,3,5]] returns [1,1,3,4,5].

02 · Analysis

Keep one pending item per nonempty stream, together with its stream ID and index. The smallest pending head is the smallest remaining value globally. Pop it, emit it, then insert only its successor. Heapify the initial heads in O(m); with N outputs, total time is O(m + N log(m+1)), auxiliary space O(m), output space O(N). Stopping after k outputs gives the chapter's top-k-across-sorted-lists variation without inspecting all N values.

03 · Solution

Reference solution

1import heapq
2
3def merge_sorted_streams(streams):
4    pending = [(values[0], stream_id, 0)
5               for stream_id, values in enumerate(streams) if values]
6    heapq.heapify(pending)
7    result = []
8    while pending:
9        value, stream_id, index = heapq.heappop(pending)
10        result.append(value)
11        index += 1
12        if index < len(streams[stream_id]):
13            heapq.heappush(pending, (streams[stream_id][index], stream_id, index))
14    return result

Delete Operations

Running Median