K-way Merge Pattern

Why this pattern matters for LeetCode

Merging K sorted lists by repeatedly finding the global minimum requires scanning the front of all K lists at each step: O(n × k). A min-heap holds exactly one element per list — the current front. Extracting the minimum is O(log k). After extraction, push the next element from the same list. Total: O(n log k) where n is the total number of elements. The heap replaces a O(k) scan with a O(log k) heap operation.

What the K-way Merge pattern is

K-way merge uses a min-heap seeded with the first element of each list. Each heap entry stores the value, which list it came from, and the index within that list. Extract the minimum from the heap — that's the next element in the merged output. Then push the next element from the same list. When a list is exhausted, don't push anything. Repeat until the heap is empty.

Reach for K-way Merge when you catch yourself thinking…

These are the internal questions that signal this pattern.

Beginner mental model

When to use K-way Merge

• ✓Merge K Sorted Lists — the canonical problem, link nodes in order using a min-heap on node values
• ✓Kth Smallest Element in a Sorted Matrix — K-way merge on the rows (or diagonals)
• ✓Find K Pairs with Smallest Sums — heap of candidate pairs, expand each row
• ✓Smallest Range Covering Elements from K Lists — sliding window variant of K-way merge
• ✓Merging K sorted log files or streams in data engineering contexts

When NOT to use K-way Merge

• ✕K = 2 lists — a simple two-pointer merge is O(n) with no heap overhead
• ✕The lists are unsorted — sort each list first, or use a different algorithm entirely
• ✕You need a specific element by position without a full merge — binary search on the answer may be faster
• ✕K is small (< 4) and n is tiny — the heap overhead isn't worth it

Better alternative: For K = 2 use the classic two-pointer merge. For finding one specific element (K-th smallest) consider binary search on the value range instead of a full merge.

JavaScript code template

Merge K Sorted Arrays — O(n log k) time, O(k) heap space

// Merge K sorted arrays into one sorted array using a min-heap.
// JavaScript needs a custom MinHeap; this shows the logic.
function mergeKSortedArrays(arrays) {
  const result = [];
  // Min-heap stores [value, arrayIndex, elementIndex]
  const heap = new MinHeap((a, b) => a[0] - b[0]);

  // Seed: push the first element of each array
  for (let i = 0; i < arrays.length; i++) {
    if (arrays[i].length > 0) {
      heap.push([arrays[i][0], i, 0]);
    }
  }

  while (!heap.isEmpty()) {
    const [val, arrIdx, elemIdx] = heap.pop(); // smallest overall
    result.push(val);

    // Push the next element from the same array
    if (elemIdx + 1 < arrays[arrIdx].length) {
      heap.push([arrays[arrIdx][elemIdx + 1], arrIdx, elemIdx + 1]);
    }
  }

  return result;
}

The heap always holds at most K elements — one per array (the current front). Each pop extracts the global minimum in O(log k). The corresponding array's next element is pushed in O(log k). After n total pops (one per element across all arrays), the heap is empty and result is fully merged. O(n log k) total.

Step-by-step thinking process

Walk through this in your head before writing code.

1. 1Seed the min-heap with the first element from each list or array, storing the value + which list it came from + the index within that list.
2. 2While the heap is not empty: pop the minimum element, add its value to the output.
3. 3If the popped element's list has a next element, push that next element into the heap.
4. 4Repeat until the heap is empty — the output is fully merged.
5. 5For K-th smallest: pop k times instead of all n times.

LeetCode-style problems that use this pattern

Practice on DSA Trainer with guided hints: no spoilers, just nudges.

• Top K Frequent Elements

  Heap of size k — push all elements and pop when the heap exceeds k to maintain the top k.

  Premium→

Coming soon

• Merge K Sorted Lists

  The canonical K-way merge: seed a min-heap with list heads, pop and re-push the successor.

  Coming soon
• Kth Smallest Element in a Sorted Matrix

  Treat each row as a sorted list; K-way merge the rows and stop after k pops.

  Coming soon
• Find K Pairs with Smallest Sums

  Seed the heap with (nums1[0] + nums2[j]) for j in 0..k-1, then expand each row of candidates.

  Coming soon

Common mistakes beginners make

• ✕Forgetting to store the source list index and element index in the heap entry — you need to know which list to advance after popping.
• ✕Pushing all elements of all lists upfront — that uses O(n) space and O(n log n) time, defeating the purpose. Push only the fronts (K elements) initially.
• ✕Using a max-heap instead of a min-heap — for merging into ascending order you want the minimum first.
• ✕Not handling empty lists at initialization — check if each list is non-empty before pushing its first element.

K-way Merge vs Pairwise Merge

Choose the right tool for the job.

Time and space complexity

Each of the n total elements is pushed and popped from the heap exactly once. Each push/pop is O(log k) since the heap holds at most k elements (one per list). Total: O(n log k). Space is O(k) for the heap plus O(n) for the output — O(n) overall if counting the result.

Frequently asked questions

Why is K-way merge O(n log k) and not O(n log n)?

The heap only ever holds k elements — one per list. Each push and pop is O(log k), not O(log n). If k << n, this is significantly faster than sorting all n elements together. For k = 10 lists of 10,000 elements each (n = 100,000), log k = ~3.3 vs log n = ~17 — 5× fewer comparisons per step.

What do I store in each heap entry?

You need the value (for comparison), the list index (to know which list to advance), and the element index (to know where in that list to look next). A tuple [value, listIndex, elementIndex] is the standard representation. For linked lists, store the node reference instead of an index.

How does K-way merge help find the K-th smallest element?

Instead of fully merging, stop after exactly K pops. Each pop gives the next-smallest element across all lists. After K pops, the last popped value is the K-th smallest. This is O(K log k) rather than O(n log k) — much faster when K is small.

Can K-way merge handle lists of different lengths?

Yes. When a list is exhausted (elementIndex + 1 >= list length), simply don't push anything after popping the last element. The heap naturally shrinks below k elements. The algorithm continues until the heap is empty.