1 · Model, solve and test · 25 MIN

Merge sorted streams with a heap

Merge sorted streams with a heap

When each input list is already sorted, a heap can hold only the next candidate from each stream. heapq.merge implements that lazy merge and retains sorted order without concatenating and sorting every element again. This exercise materializes its final list for comparison. Sorted input is a precondition; the merge function will not repair an unsorted source. Empty streams and duplicate values remain meaningful cases to test.

Track the next smallest head from each source instead of sorting a concatenated copy.

Read the example

import heapq
def solve(input):
    return list(heapq.merge(*input))
import json
print(json.dumps(solve(json.loads("[[1,4],[2,3],[1,5]]")), separators=(",", ":")))

[1,1,2,3,4,5]

Your challenge

Given a list of ascending integer lists, return all their values in ascending order, preserving duplicates. Input lists are already sorted.

Solution cost: O(n log k) for n items from k nonempty streams. time · O(k) merge state plus O(n) materialized output. space

Common trap

heapq.merge assumes its sources are sorted; it does not validate that precondition.