K-Way Merge

At a glance

The instinct

If each input is already sorted, the next element of the combined order must be one of the current heads. Nothing buried deeper in a list can beat the head of that same list. So you never need to look at more than k candidates at a time: put the k heads in a min-heap, take the smallest, and replace it with the next element from the list it came from.

That is the whole pattern. Merging two lists uses two pointers; merging k lists uses a heap as a "k-pointer comparator".

Recognise it

Not this pattern if...

• There is one unsorted array and you want top k: that is Top-K with a size-k heap.
• Only two lists: plain two pointers, no heap needed.
• The matrix question asks "does x exist?": a staircase search from a corner is O(m + n).
• You need a running median: that is Two Heaps.

Memory hack

Analogy: the relay of sorted decks. You hold k sorted card decks face up. You always take the lowest visible card, which flips the next card of that deck face up. You never need to riffle through a deck.

Say it out loud in the interview:

1. "Every source is sorted, so the global next is one of the k heads."
2. "Heap entries carry (value, which list, index in that list)."
3. "Pop, record, push the successor from the same list; stop when done or after k pops."

How it works

Seed the heap with the first element of each non-empty source. Each pop yields the next element in global order; push that element's successor if it exists. The heap never holds more than k entries, so every operation costs O(log k).

flowchart TD
  A["Push head of each non-empty list into min-heap"] --> B{"Heap empty or goal reached?"}
  B -- yes --> Z["Return result"]
  B -- no --> C["Pop smallest: value, list i, index j"]
  C --> D["Use value: append, count, or update range"]
  D --> E{"List i has index j+1?"}
  E -- yes --> F["Push list i at j+1"]
  E -- no --> B
  F --> B

Two variants change only the "use value" box:

• K-th smallest (Kth Smallest Element in a Sorted Matrix): stop after the k-th pop. You only need to seed min(k, rows) rows.
• Smallest range (Smallest Range Covering Elements from K Lists): keep curMax of everything in the heap. After each pop, the range [popped, curMax] covers all lists; update the best, push the successor, update curMax. Stop the moment any list runs out, because the window can no longer include that list.

For Find K Pairs with Smallest Sums, treat pair (i, j) as a cell of a virtual sorted grid. Seed (i, 0) for the first min(k, n1) values of i, and on each pop push (i, j + 1). This avoids duplicate pairs without a visited set.

Java template

import java.util.*;

class KWayMerge {
    // Generic merge of k sorted int arrays. Entry = {value, listIndex, elementIndex}.
    static List<Integer> merge(int[][] lists, int limit) {
        PriorityQueue<int[]> heap = new PriorityQueue<>((a, b) -> Integer.compare(a[0], b[0]));
        for (int i = 0; i < lists.length; i++) {
            if (lists[i].length > 0) heap.offer(new int[]{lists[i][0], i, 0});
        }
        List<Integer> out = new ArrayList<>();
        while (!heap.isEmpty() && out.size() < limit) {      // limit = k for "k-th smallest"
            int[] top = heap.poll();
            out.add(top[0]);                                 // problem-specific use of the value
            int i = top[1], j = top[2] + 1;
            if (j < lists[i].length) heap.offer(new int[]{lists[i][j], i, j});
        }
        return out;
    }

    // Smallest range covering one element from every list.
    static int[] smallestRange(List<List<Integer>> lists) {
        PriorityQueue<int[]> heap = new PriorityQueue<>((a, b) -> Integer.compare(a[0], b[0]));
        int curMax = Integer.MIN_VALUE;
        for (int i = 0; i < lists.size(); i++) {
            int v = lists.get(i).get(0);
            heap.offer(new int[]{v, i, 0});
            curMax = Math.max(curMax, v);
        }
        int[] best = {heap.peek()[0], curMax};
        while (true) {
            int[] top = heap.poll();
            if ((long) curMax - top[0] < (long) best[1] - best[0]) best = new int[]{top[0], curMax};
            int i = top[1], j = top[2] + 1;
            if (j == lists.get(i).size()) break;             // one list exhausted: no full cover left
            int v = lists.get(i).get(j);
            heap.offer(new int[]{v, i, j});
            curMax = Math.max(curMax, v);
        }
        return best;
    }
}

For linked lists (Merge k Sorted Lists), store the ListNode itself in the heap with a comparator on node.val, and push node.next after each pop.

Complexity

Variations

• Full merge: output every element in order. Example: Merge k Sorted Lists.
• Select the k-th: stop early after k pops. Example: Kth Smallest Element in a Sorted Matrix (binary search on value is an equally valid O(n log range) answer).
• Implicit sorted rows: generate the successor on demand instead of storing lists. Example: Find K Pairs with Smallest Sums.
• Cover-all-lists window: heap min plus tracked max. Example: Smallest Range Covering Elements from K Lists.
• Divide and conquer: merge lists in pairs like merge sort; same O(N log k), no heap.

Common mistakes

• Storing just the value in the heap, then not knowing which list to advance. Always carry the source index and position (or the node).
• Forgetting to skip empty lists or null heads when seeding, which causes NullPointerException.
• Comparator (a, b) -> a[0] - b[0] overflows with large negatives; use Integer.compare.
• In smallest-range, continuing after a list is exhausted; the remaining windows no longer contain that list.
• In k-pairs, pushing both (i+1, j) and (i, j+1) without a visited set, producing duplicate pairs.

All practice problems

4 problems on this site use this pattern, easiest first. Solve them in order and say the instinct out loud before you code.