K-way Merge Pattern — Merge K Sorted Lists With a Heap

When several already-sorted sequences must become one, the naive answers — concatenate and sort, or merge two at a time — both waste the sortedness you were handed. The pattern is a min-heap holding exactly one candidate from each sequence.

The idea

The smallest unmerged element must be at the front of one of the k lists. So keep those k front elements in a min-heap: the root is the global minimum, and when you pop it you push its successor from the same list to take its place.

import heapq

def merge_k_lists(lists):
    heap = []
    for i, node in enumerate(lists):
        if node:
            # i breaks ties: ListNode has no ordering, and Python's heap
            # falls through to comparing the next tuple element on equal keys.
            heapq.heappush(heap, (node.val, i, node))

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

    return dummy.next

ListNode mergeKLists(ListNode[] lists) {
    // Java compares with the supplied comparator, so no tie-breaker is
    // needed — unlike Python, where the heap falls through to the node.
    PriorityQueue<ListNode> heap =
        new PriorityQueue<>(Comparator.comparingInt(n -> n.val));

    for (ListNode node : lists) {
        if (node != null) heap.offer(node);
    }

    ListNode dummy = new ListNode(0), tail = dummy;
    while (!heap.isEmpty()) {
        ListNode node = heap.poll();
        tail.next = node;
        tail = node;
        if (node.next != null) heap.offer(node.next);   // push the successor
    }
    return dummy.next;   // O(N log k)
}

ListNode* mergeKLists(vector<ListNode*>& lists) {
    auto cmp = [](ListNode* a, ListNode* b) { return a->val > b->val; };
    priority_queue<ListNode*, vector<ListNode*>, decltype(cmp)> heap(cmp);

    for (ListNode* node : lists) if (node) heap.push(node);

    ListNode dummy(0);
    ListNode* tail = &dummy;
    while (!heap.empty()) {
        ListNode* node = heap.top(); heap.pop();
        tail->next = node;
        tail = node;
        if (node->next) heap.push(node->next);   // push the successor
    }
    return dummy.next;   // O(N log k)
}

function mergeKLists(lists) {
  // No built-in heap. With small k, repeatedly scanning the k heads is
  // O(N·k) but simple; for large k, implement a binary heap.
  const heads = lists.filter(Boolean);
  const dummy = { val: 0, next: null };
  let tail = dummy;

  while (heads.length) {
    let best = 0;
    for (let i = 1; i < heads.length; i++) {
      if (heads[i].val < heads[best].val) best = i;
    }
    tail.next = heads[best];
    tail = heads[best];

    if (heads[best].next) heads[best] = heads[best].next;
    else heads.splice(best, 1);
  }
  tail.next = null;
  return dummy.next;
}

That tie-breaker index is not a detail — without it, two equal values make Python compare the ListNodes themselves and raise a TypeError. Interviewers who have seen the problem before watch for it.

Why not merge pairwise

Merging list 1 into list 2, then that into list 3, and so on, re-walks the accumulated result every time: O(k × N) where N is the total number of nodes. The heap touches each node once at O(log k), giving O(N log k).

Divide-and-conquer merging — pair up the lists, merge each pair, repeat — reaches the same O(N log k) without a heap, and is worth mentioning as the alternative:

def merge_k_lists_dc(lists):
    if not lists:
        return None
    while len(lists) > 1:
        merged = []
        for i in range(0, len(lists), 2):
            second = lists[i + 1] if i + 1 < len(lists) else None
            merged.append(merge_two(lists[i], second))
        lists = merged
    return lists[0]

ListNode mergeKListsDC(ListNode[] lists) {
    if (lists.length == 0) return null;
    List<ListNode> current = new ArrayList<>(Arrays.asList(lists));

    // Each round halves the list count and touches every node once:
    // log k rounds × N work = O(N log k), same as the heap, no heap needed.
    while (current.size() > 1) {
        List<ListNode> merged = new ArrayList<>();
        for (int i = 0; i < current.size(); i += 2) {
            ListNode second = (i + 1 < current.size()) ? current.get(i + 1) : null;
            merged.add(mergeTwo(current.get(i), second));
        }
        current = merged;
    }
    return current.get(0);
}

ListNode* mergeKListsDC(vector<ListNode*> lists) {
    if (lists.empty()) return nullptr;

    // Each round halves the list count and touches every node once.
    while (lists.size() > 1) {
        vector<ListNode*> merged;
        for (size_t i = 0; i < lists.size(); i += 2) {
            ListNode* second = (i + 1 < lists.size()) ? lists[i + 1] : nullptr;
            merged.push_back(mergeTwo(lists[i], second));
        }
        lists = merged;
    }
    return lists[0];
}

function mergeKListsDC(lists) {
  if (!lists.length) return null;

  // Each round halves the list count and touches every node once:
  // log k rounds × N work = O(N log k), with no heap required.
  while (lists.length > 1) {
    const merged = [];
    for (let i = 0; i < lists.length; i += 2) {
      merged.push(mergeTwo(lists[i], lists[i + 1] ?? null));
    }
    lists = merged;
  }
  return lists[0];
}

Each round halves the number of lists, and each round touches every node once: log k rounds × N work.

Sorted matrix as k lists

Kth Smallest Element in a Sorted Matrix is k-way merge with the rows as the lists: seed

the heap with the first element of each row and pop k times.

def kth_smallest(matrix, k):
    n = len(matrix)
    heap = [(matrix[r][0], r, 0) for r in range(min(n, k))]
    heapq.heapify(heap)

    for _ in range(k - 1):
        _, r, c = heapq.heappop(heap)
        if c + 1 < n:
            heapq.heappush(heap, (matrix[r][c + 1], r, c + 1))

    return heap[0][0]

int kthSmallest(int[][] matrix, int k) {
    int n = matrix.length;
    // min(n, k) rows is enough — the answer cannot come from row k + 1.
    PriorityQueue<int[]> heap =
        new PriorityQueue<>(Comparator.comparingInt(a -> a[0]));

    for (int r = 0; r < Math.min(n, k); r++) {
        heap.offer(new int[]{matrix[r][0], r, 0});   // value, row, col
    }

    for (int i = 0; i < k - 1; i++) {
        int[] cell = heap.poll();
        if (cell[2] + 1 < n) {
            heap.offer(new int[]{matrix[cell[1]][cell[2] + 1], cell[1], cell[2] + 1});
        }
    }
    return heap.peek()[0];   // O(k log n)
}

int kthSmallest(const vector<vector<int>>& matrix, int k) {
    int n = matrix.size();
    // min(n, k) rows is enough — the answer cannot come from row k + 1.
    using Cell = tuple<int,int,int>;   // value, row, col
    priority_queue<Cell, vector<Cell>, greater<Cell>> heap;

    for (int r = 0; r < min(n, k); r++) heap.push({matrix[r][0], r, 0});

    for (int i = 0; i < k - 1; i++) {
        auto [val, r, c] = heap.top(); heap.pop();
        if (c + 1 < n) heap.push({matrix[r][c + 1], r, c + 1});
    }
    return get<0>(heap.top());   // O(k log n)
}

function kthSmallest(matrix, k) {
  const n = matrix.length;
  // Binary search on the VALUE range is the cleaner answer in JS, and it
  // wins anyway when k is large: O(n log(max - min)).
  let lo = matrix[0][0], hi = matrix[n - 1][n - 1];

  const countLessEqual = (target) => {
    let count = 0, r = n - 1, c = 0;      // staircase from the bottom-left
    while (r >= 0 && c < n) {
      if (matrix[r][c] <= target) { count += r + 1; c++; }
      else r--;
    }
    return count;
  };

  while (lo < hi) {
    const mid = lo + Math.floor((hi - lo) / 2);
    if (countLessEqual(mid) >= k) hi = mid;
    else lo = mid + 1;
  }
  return lo;
}

O(k log n). There is also a binary search on the answer solution — binary search the value range and count how many cells are ≤ mid — which is O(n log(max − min)) and wins when k is large. Knowing both, and when each is better, is the full answer.

Smallest Range Covering Elements from K Lists

The variant that shows the pattern is about more than merging. Keep one element from each list in the heap, and also track the maximum currently held. The heap root and that maximum define a range that covers all k lists by construction; record it, then advance the minimum's list and repeat. Every candidate range is examined without ever materialising the merge.

Complexity

O(N log k) time for the merge, O(k) space for the heap — the space is the reason this is the external-sorting algorithm too, where the k sequences are files far larger than memory. Divide-and-conquer is the same time bound with O(log k) recursion space instead.

Mistakes that cost the round

No tie-breaker in the heap tuple, so equal values make the comparison fall through

to an object with no ordering.

Pushing whole lists into the heap instead of one candidate each — that is

"concatenate and sort" wearing a heap costume, at O(N log N).

Merging pairwise in a loop, which is O(k × N).
Forgetting to push the successor after a pop, which silently truncates a list.
Seeding more heap entries than needed in the matrix variant — min(n, k) rows is

enough, since the answer cannot come from row k + 1.

What to drill

Merge Two Sorted Lists — the two-pointer base case.
Merge k Sorted Lists — the heap, and the divide-and-conquer alternative.
Kth Smallest Element in a Sorted Matrix — rows as lists, plus the binary-search

solution.

Smallest Range Covering Elements from K Lists — the heap with a tracked maximum.

All on the 22 DSA Patterns sheet.

Frequently asked

How do you merge k sorted lists efficiently?

Push the head of each list into a min-heap, then repeatedly pop the smallest and push that node's successor from the same list. The heap holds at most k entries, so each of the N nodes costs O(log k) — O(N log k) overall, against O(k × N) for merging the lists pairwise.

Why does my heap raise a TypeError on ListNodes?

Because two entries with equal values make Python compare the next element of the tuple, which is the node itself, and ListNode defines no ordering. Insert a unique tie-breaker — the list's index or a counter — between the value and the node.

Is a heap or divide-and-conquer better for merging k lists?

Both are O(N log k). The heap uses O(k) space and works on streams where the lists arrive incrementally; divide-and-conquer avoids the heap entirely and is often slightly faster in practice on in-memory lists. Either is a full-marks answer if you can state the complexity.

K-way Merge