Dashboard/Coding patterns/07. K-way Merge

CODING PATTERNS · LESSON 7 OF 28 · 22 MIN VIDEO · 7 PROBLEMS

K-way Merge

Module Progress (0 / 7 Problems Solved)0%
Coding patterns Track (0 / 28 Modules) · Overall 0/80 (0%)0%
⌁

Narrated HD Video Lesson (22 min) · Pro

Pattern Guide + Problem #01 + Checkpoint Quiz #1 are unlocked free below (no login required). Unlock all 80 HD video lessons and all 540 Python problems — or watch our two free sample video lessons first.

PATTERN STUDY GUIDE

K-way Merge — How the Pattern Works

K-way Merge combines k individually sorted sequences—whether explicit arrays and linked lists or implicit virtual rows generated on demand—into a single globally sorted stream without concatenating and re-sorting all N elements. By tracking one frontier cursor per sequence inside a min-heap of size at most k, the algorithm maintains the invariant that the smallest unprocessed element across the entire input must be one of those k active heads. Popping the minimum head and pushing only its immediate successor from the originating sequence lowers full-merge time from O(N log N) to O(N log k) (and O(m + n) with O(1) space when k = 2), while answering k-th smallest queries in O(k log m) time.

WHEN TO USE THIS PATTERN
  • Merging k sorted arrays, streams, or singly linked lists into a single sorted output (from the k = 2 in-place array base case to arbitrary k).
  • Finding the k-th smallest value across m sorted lists or inside a row-and-column-sorted 2D matrix without sorting all N elements.
  • Extracting the k smallest pairs, sums, or fractions f(A[i], B[j]) across two sorted arrays A and B, where fixing index i produces a monotonically sorted virtual row over j.
  • Generating an ascending sequence of numbers closed under multiplication by a fixed set of k prime factors (Ugly / Super Ugly number streams).
COMMON INTERVIEW PITFALLS
  • Pushing non-comparable objects directly in heap tuples: in Merge K Sorted Lists, pushing (node.val, node) raises a TypeError in Python whenever two nodes tie on node.val; always insert a unique integer tie-breaker such as (node.val, list_idx, node).
  • Enqueuing duplicate coordinates in 2D pair searches: pushing both (i + 1, j) and (i, j + 1) on each pop visits (1, 1) twice unless guarded by a visited set; instead, seed (i, 0) for 0 <= i < min(k, len(A)) and advance strictly along (i, j + 1).
  • Ordering rational numbers with floating-point division: float precision loss can misorder close fractions a / b and c / d; implement custom __lt__ comparison via exact integer cross-multiplication a * d < c * b.
  • Double-counting cross-stream duplicates in generative merges: in Super Ugly Number, products like 2 * 7 and 7 * 2 both yield 14; skip appending when val == result[-1], yet still advance that factor's cursor j + 1.
Explicit K-Way Merge for K-th Smallest ElementStreaming elements in global ascending order across m sorted lists and terminating early on the k-th pop.
from heapq import heapify, heappush, heappop

def kth_across_lists(lists, k):
    heap = [(s[0], i, 0) for i, s in enumerate(lists) if s]
    heapify(heap)
    while heap:
        val, i, j = heappop(heap)
        k -= 1
        if k == 0:
            return val
        if j + 1 < len(lists[i]):
            heappush(heap, (lists[i][j + 1], i, j + 1))
Implicit Virtual-Row Merge (Top-K Pairs / Combinations)Enumerating the k smallest combinations across two sorted arrays A and B without materializing the O(|A| * |B|) grid.
from heapq import heapify, heappush, heappop

def k_smallest_virtual_rows(A, B, k):
    heap = [(A[i] + B[0], i, 0) for i in range(min(k, len(A)))]
    heapify(heap)
    res = []
    while heap and len(res) < k:
        _, i, j = heappop(heap)
        res.append([A[i], B[j]])
        if j + 1 < len(B):
            heappush(heap, (A[i] + B[j + 1], i, j + 1))
    return res
Reverse Two-Pointer In-Place Merge (k = 2 Base Case)Merging two sorted arrays in O(m + n) time and O(1) extra space when trailing empty capacity sits at the end of nums1.
def merge_from_back(nums1, m, nums2, n):
    p1, p2, write = m - 1, n - 1, m + n - 1
    while p2 >= 0:
        if p1 >= 0 and nums1[p1] > nums2[p2]:
            nums1[write] = nums1[p1]
            p1 -= 1
        else:
            nums1[write] = nums2[p2]
            p2 -= 1
        write -= 1

01. Merge Sorted Array

Optimal Target: O(m + n) time · O(1) space

Given two integer arrays nums1 and nums2 sorted in non-decreasing order, along with integers m and n representing the number of initialized elements in nums1 and nums2 respectively, merge nums2 into nums1 in-place so that nums1 is sorted in non-decreasing order. The array nums1 has total length m + n, where the first m elements hold the values to merge and the trailing n slots are empty placeholders (0) reserved for the result.

EXAMPLE 1
Input: nums1 = [2, 5, 8, 0, 0, 0], m = 3, nums2 = [1, 6, 9], n = 3
Output: [1, 2, 5, 6, 8, 9]
Explanation: Filling from index 5 leftward compares 8 vs 9 (writes 9), 8 vs 6 (writes 8), 5 vs 6 (writes 6), 5 vs 1 (writes 5), 2 vs 1 (writes 2), and finally copies 1 into index 0.
VISUAL INPUT
nums1
258
nums2
169
AUTOMATED TEST SUITE
Test Case 1
Input: [2, 5, 8, 0, 0, 0], 3, [1, 6, 9], 3
Expected: [1, 2, 5, 6, 8, 9]
Test Case 2
Input: [0], 0, [1], 1
Expected: [1]
Test Case 3
Input: [4, 5, 6, 0, 0], 3, [1, 2], 2
Expected: [1, 2, 4, 5, 6]
Pattern Trigger Hint ("How to Spot It")

merge in place, room at the end → fill from back

Python 3.14 Runtime Ready

Click ▶ Run Tests (or press ⌘+Enter) to execute merge against all 3 test cases in WebAssembly Python.

Pattern Checkpoint Quizzes

CHECKPOINT QUIZ #1

You're merging ten sorted lists. What's the most entries the heap ever holds at once?