You already know how to merge two sorted lists in $O(n)$ — it’s the merge step from merge sort. The interview twist is merging $k$ of them at once. Doing that with repeated two-way merges works, but a min-heap that always holds one candidate per list turns it into a single clean pass, and it’s the pattern behind an entire family of “smallest across k sequences” questions.

What you’ll learn

• Why merging $k$ lists two-at-a-time is worse than it looks.
• The k-way merge template: a min-heap of (value, list_index, element_index)(value, list_index, element_index) tuples, one entry per list.
• How the same heap-of-heads idea generalizes to a sorted matrix, not just a list of lists.
• Why the pattern costs $O(N \log k)$, where $N$ is the total element count.

The naive approach, and why it’s worse than it looks

Merging $k$ sorted lists two at a time — merge list 1 into list 2, merge that into list 3, and so on — costs $O(N \cdot k)$ in the worst case: each of the $k$ merge passes touches close to all $N$ elements. As $k$ grows, that quadratic-ish blowup gets painful. The fix is to never compare more than $k$ candidates at once, no matter how many elements are still buried inside each list.

The pattern: one heap slot per list

Keep a min-heap with at most one entry per list — always its current smallest unconsumed element. Popping the heap’s minimum gives you the next overall smallest value; you then push that list’s next element back in to replace it. The heap tuple carries (value, list_idx, elem_idx)(value, list_idx, elem_idx) so you always know exactly which list to advance.

import heapq
 
def merge_k_sorted(lists):
    result = []
    heap = []
 
    # Seed the heap with each list's first element (skip empty lists).
    for i, lst in enumerate(lists):
        if lst:
            heapq.heappush(heap, (lst[0], i, 0))
 
    while heap:
        val, list_idx, elem_idx = heapq.heappop(heap)
        result.append(val)
 
        # Advance the list this value came from, if it has more elements.
        if elem_idx + 1 < len(lists[list_idx]):
            next_val = lists[list_idx][elem_idx + 1]
            heapq.heappush(heap, (next_val, list_idx, elem_idx + 1))
 
    return result
 
 
lists = [[1, 4, 7], [2, 5, 8], [3, 6, 9]]
print(merge_k_sorted(lists))   # expect [1, 2, 3, 4, 5, 6, 7, 8, 9]

import heapq
 
def merge_k_sorted(lists):
    result = []
    heap = []
 
    # Seed the heap with each list's first element (skip empty lists).
    for i, lst in enumerate(lists):
        if lst:
            heapq.heappush(heap, (lst[0], i, 0))
 
    while heap:
        val, list_idx, elem_idx = heapq.heappop(heap)
        result.append(val)
 
        # Advance the list this value came from, if it has more elements.
        if elem_idx + 1 < len(lists[list_idx]):
            next_val = lists[list_idx][elem_idx + 1]
            heapq.heappush(heap, (next_val, list_idx, elem_idx + 1))
 
    return result
 
 
lists = [[1, 4, 7], [2, 5, 8], [3, 6, 9]]
print(merge_k_sorted(lists))   # expect [1, 2, 3, 4, 5, 6, 7, 8, 9]

How it works

  graph TD
    L0["List 0 head: 1"] --> H["min-heap: one (value, list_idx, elem_idx) per list"]
    L1["List 1 head: 2"] --> H
    L2["List 2 head: 3"] --> H
    H --> P["pop the smallest -> append to result"]
    P --> N["push that list's NEXT element back in"]
    N --> H

The heap never holds more than $k$ items at once — one per list — no matter how large each individual list is. Every element from every list gets pushed and popped from the heap exactly once over the whole run.

Worked example: Kth Smallest Element in a Sorted Matrix

A matrix with sorted rows (and sorted columns) is just $k$ sorted lists in disguise — one list per row. Seed the heap with the first element of every row, then pop $k$ times, advancing along each row exactly like before.

import heapq
 
def kth_smallest_in_matrix(matrix, k):
    n = len(matrix)
    # Seed the heap with the first element of every row.
    heap = [(matrix[row][0], row, 0) for row in range(n)]
    heapq.heapify(heap)
 
    val = None
    for _ in range(k):
        val, row, col = heapq.heappop(heap)
        if col + 1 < n:
            heapq.heappush(heap, (matrix[row][col + 1], row, col + 1))
    return val
 
 
matrix = [
    [1, 5, 9],
    [10, 11, 13],
    [12, 13, 15],
]
print(kth_smallest_in_matrix(matrix, 8))   # expect 13

import heapq
 
def kth_smallest_in_matrix(matrix, k):
    n = len(matrix)
    # Seed the heap with the first element of every row.
    heap = [(matrix[row][0], row, 0) for row in range(n)]
    heapq.heapify(heap)
 
    val = None
    for _ in range(k):
        val, row, col = heapq.heappop(heap)
        if col + 1 < n:
            heapq.heappush(heap, (matrix[row][col + 1], row, col + 1))
    return val
 
 
matrix = [
    [1, 5, 9],
    [10, 11, 13],
    [12, 13, 15],
]
print(kth_smallest_in_matrix(matrix, 8))   # expect 13

The $k$-th pop off the heap is, by construction, the $k$-th smallest value across the whole matrix — you never sort all $9$ elements to get there.

Time and space complexity

Compare that to sorting all $N$ elements directly: $O(N \log N)$. When $k \ll N$ — a handful of long lists, or a matrix with far more entries than rows — the k-way merge is meaningfully cheaper.

When to use it

• You have $k$ already-sorted sequences (lists, arrays, or matrix rows) and need them combined into one sorted output, or need only the $k$-th overall smallest/largest value without materializing the full merge.
• $k$ is small relative to the total element count $N$ — the heap’s $O(\log k)$ cost per step is what makes this cheaper than one big sort.
• The “list” doesn’t have to be a Python list — linked lists, matrix rows, or even ranges from kk different iterators all work the same way, as long as each one is individually sorted and you can ask for “the next element after this one.”

Practice — real LeetCode problems

Each exercise is the actual LeetCode problem with its real method signature and LeetCode’s own examples as the test. Write the body, press Run, and match the expected output.

LC 23 — Merge k Sorted Lists · Hard

Problem. Merge kk sorted linked lists into one sorted list and return its head.

Constraints. 0 <= k <= 10^40 <= k <= 10^4, 0 <= len(each list) <= 5000 <= len(each list) <= 500, total nodes up to 10^410^4.

Examples. [[1,4,5],[1,3,4],[2,6]][[1,4,5],[1,3,4],[2,6]] gives [1,1,2,3,4,4,5,6][1,1,2,3,4,4,5,6] · [][] gives [][] · [[]][[]] gives [][]

LC 378 — Kth Smallest Element in a Sorted Matrix · Medium

Problem. Given an n x nn x n matrix whose rows and columns are each sorted ascending, return the kkth smallest element (in overall sorted order, counting duplicates).

Constraints. 1 <= n <= 3001 <= n <= 300, 1 <= k <= n^21 <= k <= n^2.

Examples. matrix = [[1,5,9],[10,11,13],[12,13,15]], k = 8matrix = [[1,5,9],[10,11,13],[12,13,15]], k = 8 gives 1313 · matrix = [[-5]], k = 1matrix = [[-5]], k = 1 gives -5-5

LC 373 — Find K Pairs with Smallest Sums · Medium

Problem. Given two sorted arrays and an integer kk, return the kk pairs (u, v)(u, v) with uu from nums1nums1 and vv from nums2nums2 that have the smallest sums.

Constraints. 1 <= len(nums1), len(nums2) <= 10^51 <= len(nums1), len(nums2) <= 10^5, both sorted ascending, 1 <= k <= 10^41 <= k <= 10^4.

Examples. nums1 = [1,7,11], nums2 = [2,4,6], k = 3nums1 = [1,7,11], nums2 = [2,4,6], k = 3 gives [[1,2],[1,4],[1,6]][[1,2],[1,4],[1,6]] · nums1 = [1,1,2], nums2 = [1,2,3], k = 2nums1 = [1,1,2], nums2 = [1,2,3], k = 2 gives [[1,1],[1,1]][[1,1],[1,1]]

LeetCode problem set

Recap

• Merging $k$ sorted sequences two at a time costs up to $O(N \cdot k)$ — a single heap holding one candidate per sequence does it in $O(N \log k)$ instead.
• The heap tuple is (value, list_idx, elem_idx)(value, list_idx, elem_idx) — the indices both identify where to advance next and break ties Python can compare safely.
• Every element is pushed and popped from the heap exactly once over the whole run.
• The same idea covers linked lists, plain arrays, matrix rows, and even lazily generated pairs — anything you can ask “what’s your next smallest element?”

Next: Binary Search on Answer — turning binary search from an array lookup into a tool for optimization problems.