088. Merge K Sorted Arrays

Why this mechanism works

Only the first unread value from each source can be its next contribution. A heap chooses the smallest among those k frontiers. After consuming one source's frontier, insert only its next value. This generalizes the two-source merge without placing every input value in the heap at once.

State and boundaries

heap contains one (value,source,position) entry per nonexhausted source. output is the sorted merge of all consumed prefixes.

Protocol

1. Seed the first value of each nonempty source.
2. Pop the smallest frontier.
3. Append its value.
4. Push the next value from that same source if present.
5. Continue until the heap is empty.

Visualization

frontiers: A:1, B:2, C:0
pop C:0 -> replenish C:5
new frontiers: A:1, B:2, C:5

Python implementation

import heapq

def merge_k_arrays(arrays):
    heap = []
    for source, values in enumerate(arrays):
        if values:
            heap.append((values[0], source, 0))
    heapq.heapify(heap)
    output = []
    while heap:
        value, source, position = heapq.heappop(heap)
        output.append(value)
        position += 1
        if position < len(arrays[source]):
            heapq.heappush(heap, (arrays[source][position], source, position))
    return output

Worked execution

Recorded state changes after statements; L numbers refer to the solution file. Long traces are explicitly condensed.

L4 merge_k_arrays: heap = []
arrays=[[1, 4], [2, 3], [0, 5]]; heap=[]

L5 merge_k_arrays: for source, values in enumerate(arrays):
arrays=[[1, 4], [2, 3], [0, 5]]; heap=[]; source=0; values=[1, 4]

L7 merge_k_arrays: heap.append((values[0], source, 0))
arrays=[[1, 4], [2, 3], [0, 5]]; heap=[(1, 0, 0)]; source=0; values=[1, 4]

L5 merge_k_arrays: for source, values in enumerate(arrays):
arrays=[[1, 4], [2, 3], [0, 5]]; heap=[(1, 0, 0)]; source=1; values=[2, 3]

L7 merge_k_arrays: heap.append((values[0], source, 0))
arrays=[[1, 4], [2, 3], [0, 5]]; heap=[(1, 0, 0), (2, 1, 0)]; source=1; values=[2, 3]

L5 merge_k_arrays: for source, values in enumerate(arrays):
arrays=[[1, 4], [2, 3], [0, 5]]; heap=[(1, 0, 0), (2, 1, 0)]; source=2; values=[0, 5]

L7 merge_k_arrays: heap.append((values[0], source, 0))
arrays=[[1, 4], [2, 3], [0, 5]]; heap=[(1, 0, 0), (2, 1, 0), (0, 2, 0)]; source=2; values=[0, 5]

L8 merge_k_arrays: heapq.heapify(heap)
arrays=[[1, 4], [2, 3], [0, 5]]; heap=[(0, 2, 0), (2, 1, 0), (1, 0, 0)]; source=2; values=[0, 5]

... 18 intermediate state changes omitted ...

L13 merge_k_arrays: position += 1
arrays=[[1, 4], [2, 3], [0, 5]]; heap=[(5, 2, 1)]; source=0; values=[0, 5]; output=[0, 1, 2, 3, 4]; value=4; position=2

L11 merge_k_arrays: value, source, position = heapq.heappop(heap)
arrays=[[1, 4], [2, 3], [0, 5]]; heap=[]; source=2; values=[0, 5]; output=[0, 1, 2, 3, 4]; value=5; position=1

L12 merge_k_arrays: output.append(value)
arrays=[[1, 4], [2, 3], [0, 5]]; heap=[]; source=2; values=[0, 5]; output=[0, 1, 2, 3, 4, 5]; value=5; position=1

L13 merge_k_arrays: position += 1
arrays=[[1, 4], [2, 3], [0, 5]]; heap=[]; source=2; values=[0, 5]; output=[0, 1, 2, 3, 4, 5]; value=5; position=2

L4 merge_k_arrays: heap = []
arrays=[[], [2, 2], []]; heap=[]

L5 merge_k_arrays: for source, values in enumerate(arrays):
arrays=[[], [2, 2], []]; heap=[]; source=0; values=[]

L5 merge_k_arrays: for source, values in enumerate(arrays):
arrays=[[], [2, 2], []]; heap=[]; source=1; values=[2, 2]

L7 merge_k_arrays: heap.append((values[0], source, 0))
arrays=[[], [2, 2], []]; heap=[(2, 1, 0)]; source=1; values=[2, 2]

L5 merge_k_arrays: for source, values in enumerate(arrays):
arrays=[[], [2, 2], []]; heap=[(2, 1, 0)]; source=2; values=[]

L9 merge_k_arrays: output = []
arrays=[[], [2, 2], []]; heap=[(2, 1, 0)]; source=2; values=[]; output=[]

L11 merge_k_arrays: value, source, position = heapq.heappop(heap)
arrays=[[], [2, 2], []]; heap=[]; source=1; values=[]; output=[]; value=2; position=0

L12 merge_k_arrays: output.append(value)
arrays=[[], [2, 2], []]; heap=[]; source=1; values=[]; output=[2]; value=2; position=0

... 1 intermediate state changes omitted ...

L15 merge_k_arrays: heapq.heappush(heap, (arrays[source][position], source, position))
arrays=[[], [2, 2], []]; heap=[(2, 1, 1)]; source=1; values=[]; output=[2]; value=2; position=1

L11 merge_k_arrays: value, source, position = heapq.heappop(heap)
arrays=[[], [2, 2], []]; heap=[]; source=1; values=[]; output=[2]; value=2; position=1

L12 merge_k_arrays: output.append(value)
arrays=[[], [2, 2], []]; heap=[]; source=1; values=[]; output=[2, 2]; value=2; position=1

L13 merge_k_arrays: position += 1
arrays=[[], [2, 2], []]; heap=[]; source=1; values=[]; output=[2, 2]; value=2; position=2

Why the solution is correct

The minimum source frontier is no larger than any unread value, so it is the next global output value. Replacing only its source frontier preserves the one-entry-per-source representation. Exhaustion means every occurrence has been consumed exactly once.

Time and space

O(N log(k+1)) time and O(k) frontier space plus O(N) output, where N is total input length.

Common mistakes

Pushing entire source arrays into the heap loses the bounded-frontier advantage. Omitting a source identifier makes it impossible to replenish the correct stream.

Reasoning card

Transfer exercise

Replace lists with iterators so the same frontier algorithm can merge files or streams larger than memory.