Merge K Sorted Runs
Problem
You are given k lists, each sorted in ascending order, and some of them may be empty. Combine them into one ascending list holding every value, duplicates included. Read each list only from the front and keep no more than one waiting value per list at any time.
Examples
Input: lists = [[1, 4, 5], [1, 3, 4], [2, 6]]
Output: [1, 1, 2, 3, 4, 4, 5, 6]Input: lists = [[], [0], []]
Output: [0]
Why: empty lists simply contribute nothingInput: lists = []
Output: []
Why: edge case, no lists at allHints
0 / 3
Pouring everything into one list and sorting ignores the fact that every list is already in order.
At any moment, the next value of the output must be the front value of one of the lists. You only ever need the smallest of those k front values.
Put the front value of each non-empty list into a min-heap, tagged with its list and position. Pop the smallest, append it to the output, and push the next value from the same list if there is one. Stop when the heap is empty.
Solution
The next output value is always the smallest of the current front values, so a min-heap holding exactly one front value per list delivers it in O(log k). Each entry carries its list index and position, so after a pop the heap is refilled from the list that just gave up a value, which keeps the one-per-list rule. Tagging with the list index also breaks ties between equal values without ever comparing anything else. With n values in total, time is O(n log k) and the heap holds at most k entries.
import heapq
def merge_runs(lists):
heap = [(run[0], i, 0) for i, run in enumerate(lists) if run]
heapq.heapify(heap) # one front value per list
out = []
while heap:
value, i, j = heapq.heappop(heap)
out.append(value)
if j + 1 < len(lists[i]): # refill from the list just used
heapq.heappush(heap, (lists[i][j + 1], i, j + 1))
return out
print(merge_runs([[1, 4, 5], [1, 3, 4], [2, 6]])) # -> [1, 1, 2, 3, 4, 4, 5, 6]
print(merge_runs([[], [0], []])) # -> [0]
print(merge_runs([])) # -> []Stuck on the idea rather than the code? K-Way Merge covers it.