Merge K Sorted Structures

Merging K Sorted Structures with a Min-Heap

LeetCode 23 asks you to merge K sorted lists into a single sorted output. The naive instinct is to collect every element into one array and sort it, which costs $O(N \log N)$ where N is the total number of elements. That works, but it throws away all the structural information you already have: the lists are already sorted, and you should be able to exploit that.

The right tool is a min-heap (priority queue). The core insight: at any point during the merge, the globally smallest remaining element must be the smallest element at the current front of one of your K lists. You never need to look further into any list than its current head.

Why a Heap and Not Something Simpler

If you had just two sorted lists, a simple two-pointer merge would work in $O(N)$ time. With K lists, you could do the same thing iteratively, scanning the front of all K lists to find the minimum, but that costs $O(K)$ per element, giving $O(N \cdot K)$ total. A heap reduces that per-element cost to $O(\log K)$, yielding $O(N \log K)$ overall. For large K, this matters: merging 1000 lists of 1000 elements each is 1,000,000 × 10 vs 1,000,000 × 1000 operations.

The Algorithm

The approach has three phases:

Seed the heap. Push the first element from each non-empty list, tagged with the list index (and the element's position within that list, if needed). The heap now contains at most K elements.

Drain the heap. Pop the minimum. That value is the next element in the globally sorted order, so append it to your result. Then push that element's successor from the same source list (if one exists).

Terminate. Once the heap is empty, all lists are exhausted and the result is complete.

The heap never grows beyond K elements because you add one element only when you remove one.

Walked Example

Say you have three sorted lists:

A = [1, 4, 7]
B = [2, 5, 8]
C = [3, 6, 9]

After seeding, the heap contains (1, 0, 0), (2, 1, 0), (3, 2, 0), tuples of (value, list index, element index).

• Pop (1, 0, 0). Output: [1]. Push (4, 0, 1). Heap now has (2,1,0), (3,2,0), (4,0,1).
• Pop (2, 1, 0). Output: [1,2]. Push (5, 1, 1). Heap: (3,2,0), (4,0,1), (5,1,1).
• Pop (3, 2, 0). Output: [1,2,3]. Push (6, 2, 1).
• Continue: 4, 5, 6, 7, 8, 9.

At every step, exactly one element is removed and at most one is added. The heap size stays at 3 throughout.

The Code

import heapq

def merge_k_sorted_lists(lists):
    heap = []
    for i, node in enumerate(lists):
        if node:
            heapq.heappush(heap, (node.val, i, node))

    dummy = curr = ListNode(0)
    while heap:
        val, i, node = heapq.heappop(heap)
        curr.next = node
        curr = curr.next
        if node.next:
            heapq.heappush(heap, (node.next.val, i, node.next))

    return dummy.next

The list index i is the tie-breaker. Python's heap compares tuple elements left to right, so if two nodes have the same value it will try to compare the ListNode objects directly, which raises a TypeError since nodes aren't orderable. Including i as the second element guarantees the comparison always resolves before reaching the node.

For array-based sources the structure is the same, but you track a position index instead of following .next pointers:

def merge_k_sorted_arrays(arrays):
    heap = []
    for i, arr in enumerate(arrays):
        if arr:
            heapq.heappush(heap, (arr[0], i, 0))

    result = []
    while heap:
        val, i, j = heapq.heappop(heap)
        result.append(val)
        if j + 1 < len(arrays[i]):
            heapq.heappush(heap, (arrays[i][j + 1], i, j + 1))

    return result

Complexity Analysis

• Time: $O(N \log K)$. Each of the N total elements is pushed once and popped once. Each push/pop costs $O(\log K)$ because the heap contains at most K elements.
• Space: $O(K)$. The heap itself holds at most K entries. The output array is $O(N)$ but that is required output, not overhead.

Compared to sort-everything: $O(N \log N)$ versus $O(N \log K)$. Since $K \leq N$, $\log K \leq \log N$, so the heap approach is never worse and is strictly better when K is much smaller than N.

Variants Worth Knowing

Ugly Number II. Generate the nth number whose only prime factors are 2, 3, and 5. This is equivalent to merging three infinite sorted streams: multiples of 2, multiples of 3, multiples of 5. You use three pointers (or a heap of size 3) and advance the pointer whose product was just consumed, taking care to deduplicate when multiple streams produce the same value.

Smallest Range Covering K Lists. You want the smallest window [lo, hi] such that each of the K lists contains at least one element in the window. The trick: maintain a min-heap of K current front elements (giving you lo = heap[0]) and track the running maximum of all currently active elements as hi. At each step, pop the minimum and push the next element from that list, updating hi. When any list is exhausted you stop, since you can no longer cover all K lists.

def smallest_range(nums):
    heap = [(row[0], i, 0) for i, row in enumerate(nums)]
    heapq.heapify(heap)
    hi = max(row[0] for row in nums)
    best_lo, best_hi = heap[0][0], hi

    while True:
        lo, i, j = heapq.heappop(heap)
        if j + 1 == len(nums[i]):
            break
        nxt = nums[i][j + 1]
        heapq.heappush(heap, (nxt, i, j + 1))
        hi = max(hi, nxt)
        lo = heap[0][0]
        if hi - lo < best_hi - best_lo:
            best_lo, best_hi = lo, hi

    return [best_lo, best_hi]

The pattern, seed a K-element heap, pop minimum, push successor, repeat, applies cleanly to any problem that asks you to weave together multiple sorted sources.

Recognizing this pattern

You're probably looking at merge-K-sorted when:

• You're given K sorted sequences (lists, arrays, iterators) and asked to merge them or extract a small prefix from the merged order.
• The natural answer requires looking at the current head of each sequence and repeatedly picking the smallest.
• The problem asks for the smallest range covering at least one element from each of K sorted lists.
• You're producing the Kth smallest element of a Cartesian product or matrix whose rows/columns are individually sorted.

Common templates:

• Heap of K list heads: seed with one node per list, pop, push node.next. Example: Merge k Sorted Lists.
• Sorted-matrix Kth smallest via row heads: heap entries carry (value, row, col). Example: Kth Smallest Element in a Sorted Matrix.
• Smallest range covering one element per list: track current max while popping current min from a K-heap. Example: Smallest Range Covering Elements from K Lists.
• Sum pairs from two sorted arrays: heap of frontier (i, j) pairs with visited set. Example: Find K Pairs with Smallest Sums.