SkillByAIOpen interactive version →

Lesson 42 / 42

K-way Merge

Merge k sorted lists efficiently using a min-heap that always holds the next-smallest candidate from each list.

Beyond two-way merge

Merging two sorted lists is O(n) with two pointers. For k sorted lists, a min-heap holding one candidate per list generalizes this: always pop the smallest, then push that list's next element.

Merge k sorted lists

Seed the heap with the first element of each list (tagged with its list/index so we know where to fetch the next value from).

import heapq

def merge_k_sorted(lists):
    heap = []
    for i, lst in enumerate(lists):
        if lst:
            heapq.heappush(heap, (lst[0], i, 0))

    result = []
    while heap:
        val, i, j = heapq.heappop(heap)
        result.append(val)
        if j + 1 < len(lists[i]):
            heapq.heappush(heap, (lists[i][j + 1], i, j + 1))
    return result

Output:

merge_k_sorted([[1,4,5],[1,3,4],[2,6]])
# [1, 1, 2, 3, 4, 4, 5, 6]

Complexity & uses

With n total elements across k lists, this runs in O(n log k) — the heap never holds more than k elements. Used for merging sorted log files, external sorting, and the 'smallest range covering k lists' family of problems.

Final quiz 1 of 8

Final quiz

Quick check: What is the time complexity of binary search?

  • O(n)
  • O(1)
  • O(log n)
  • O(n log n)
Answer

O(log n) — Each step halves the search range.

Final quiz 2 of 8

Final quiz

Quick check: Which structure gives average O(1) lookup by key?

  • Linked list
  • Stack
  • Sorted array scan
  • Hash map
Answer

Hash map — A hash function maps keys to buckets.

Final quiz 3 of 8

Final quiz

Quick check: Which structure suits balanced-bracket checks?

  • Stack
  • Queue
  • Trie
  • Heap
Answer

Stack — Push openings, pop on closings.

Final quiz 4 of 8

Final quiz

Quick check: Which traversal finds shortest paths in an unweighted graph?

  • DFS
  • BFS
  • In-order
  • Post-order
Answer

BFS — BFS explores level by level.

Final quiz 5 of 8

Final quiz

Quick check: When does Dijkstra's algorithm give correct results?

  • The graph is a tree
  • The graph is undirected
  • All edge weights are non-negative
  • The graph is small
Answer

All edge weights are non-negative — Negative edges need Bellman-Ford.

Final quiz 6 of 8

Final quiz

Quick check: What is the worst-case time of merge sort?

  • O(n^2)
  • O(n)
  • O(log n)
  • O(n log n)
Answer

O(n log n) — It always splits and merges evenly.

Final quiz 7 of 8

Final quiz

Quick check: Which pattern handles longest-substring problems in one pass?

  • Sliding window
  • Union-find
  • Bit manipulation
  • K-way merge
Answer

Sliding window — Expand right, shrink left as needed.

Final quiz 8 of 8

Final quiz

Quick check: What makes a problem suitable for dynamic programming?

  • Random inputs
  • Overlapping subproblems and optimal substructure
  • Large strings
  • Sorted data
Answer

Overlapping subproblems and optimal substructure — Store subproblem answers to avoid recomputation.