Python 3.11+
The examples use the standard Python syntax and containers supported by the browser Judge; the K-way Merge invariant is independent of a minor Python release.
Verify in Python docs(opens in a new tab)Pattern1 Practice1 Interview
K-way Merge
Use a heap of current heads to merge or traverse multiple sorted sequences efficiently. Learn its decision rule, maintained state, Python cost model, and transfer from a focused drill to a full Interview Problem.
Recognize it when
Consider K-way Merge when the prompt's constraints and required operations match this shape: Use a heap of current heads to merge or traverse multiple sorted sequences efficiently.
On this page · Put One Candidate per Source on the Heap
Checking your account…
Sign in to save your code and progress across devices. The lesson and problem statement remain public.
K-way Merge Code Labs
Put One Candidate per Source on the Heap
For k sorted sources, only the first unconsumed value from each source can be the global next value. A min-heap stores that frontier in O(k) space.
Carry Source and Position
Each heap entry needs value, source identity, and position. Source and position provide deterministic tie-breaking and tell the algorithm exactly which successor to expose.
Trace K-Way Heap Frontiers
Reference
import heapq
def merge_frontier_trace(sources):
heap=[]; trace=[]
for source,values in enumerate(sources):
if values: heapq.heappush(heap,(values[0],source,0))
while heap:
trace.append([list(item) for item in sorted(heap)])
value,source,position=heapq.heappop(heap)
if position+1<len(sources[source]): heapq.heappush(heap,(sources[source][position+1],source,position+1))
return tracePractice
Implement merge_frontier_trace(sources). Return sorted heap triples [value,source,position] before each winner is removed.
Public tests
- Keep one candidate per source
Loading interactive editor.If it does not appear, the reference and starter code remain readable.Reload editor
Advance Only the Winning Source
Pop the smallest frontier item, append it, then push only the next item from that same source. Other source fronts remain valid. Total time is O(n log k), where n is the total number of values.
Merge Sorted Sources
Reference
import heapq
def merge_sorted_sources(sources):
heap=[]; result=[]
for source,values in enumerate(sources):
if values: heapq.heappush(heap,(values[0],source,0))
while heap:
value,source,position=heapq.heappop(heap); result.append(value)
if position+1<len(sources[source]): heapq.heappush(heap,(sources[source][position+1],source,position+1))
return resultPractice
Implement merge_sorted_sources(sources). Return one sorted list without mutating sources.
Public tests
- Advance only the winning source
Loading interactive editor.If it does not appear, the reference and starter code remain readable.Reload editor
Choose K Way Merge or Concatenate and Sort
Use k-way merge when sources are already sorted, streamed, or too large to concatenate. Concatenate and sort is simpler when inputs are small and random access is cheap, but costs O(n log n).
Explain It in an Interview
Say: “The heap contains exactly one next candidate per nonempty source. After the minimum wins, only that source can reveal a new candidate.” Cover empty sources, equal values, and whether input iterators may be consumed.
Python Version Note
Complexity & Invariants
Interview bounds depend on the stated representation, input model, and real Python operations.
| Operation | Average | Worst | Interview note |
|---|---|---|---|
| K-way Merge decision loop | O(n log k) | O(n log k) | Maintain one heap frontier per non-empty sorted row and advance only the row that supplies the minimum. |
Space
O(k) for the focused Merge Sorted Rows implementation.
Assumptions
- The smallest unseen value must be at one row frontier, so each heap pop is the next global value. Replacing it with that row’s next value preserves the invariant until every row is exhausted.
- The bound includes real Python operations; no repeated slicing, linear list membership, or hidden sorting is treated as free.
Invariants Worth Saying Aloud
- State the precise K-way Merge invariant before coding and preserve it after every update, traversal step, or recursive return.
- The heap contains at most one next unseen item per source.
- The emitted prefix is globally sorted and complete.
- Seed one heap entry per non-empty source. Preserve this property after every transition.
- Advance only the source that produced the minimum. Preserve this property after every transition.
When To Use Or Avoid K-way Merge
Use It When
- Use K-way Merge when the prompt exposes the ordering, monotonicity, recurrence, or constraint that makes this decision safe.
- Use it when the heap contains at most one next unseen item per source.
Choose Another Tool When
- Avoid K-way Merge when its decision rule cannot eliminate work or preserve the required state.
- Avoid forcing the label onto a prompt whose simpler direct scan already meets the constraints.
Common Pitfalls
These are the mistakes most likely to survive a happy-path example and fail a boundary case.
Moving state without a proof
Applying the pattern without proving its ordering, monotonicity, or window invariant can silently miss valid candidates.
Prevent it: Write the decision rule beside the loop and verify it against Merge Sorted Rows before optimizing.
Avoid
def merge_sorted_rows(rows):
passUse instead
import heapq
def merge_sorted_rows(rows):
heap = []
for row_index, row in enumerate(rows):
if row:
heapq.heappush(heap, (row[0], row_index, 0))
merged = []
while heap:
value, row_index, element_index = heapq.heappop(heap)
merged.append(value)
next_index = element_index + 1
if next_index < len(rows[row_index]):
heapq.heappush(heap, (rows[row_index][next_index], row_index, next_index))
return mergedWhere you will hit this: Merge Sorted Rows(opens in a new tab)
Breaking the maintained state
Seeds empty rows unconditionally and raises instead of skipping them.
Prevent it: Use the public tests and preserve this state: The heap contains at most one next unseen item per source.
Avoid
import heapq
def merge_sorted_rows(rows):
h=[(row[0],i,0) for i,row in enumerate(rows)]
heapq.heapify(h)
return [heapq.heappop(h)[0] for _ in range(len(h))]Use instead
import heapq
def merge_sorted_rows(rows):
heap = []
for row_index, row in enumerate(rows):
if row:
heapq.heappush(heap, (row[0], row_index, 0))
merged = []
while heap:
value, row_index, element_index = heapq.heappop(heap)
merged.append(value)
next_index = element_index + 1
if next_index < len(rows[row_index]):
heapq.heappush(heap, (rows[row_index][next_index], row_index, next_index))
return mergedWhere you will hit this: Merge Sorted Rows(opens in a new tab)
Hiding Python work in the hot path
Python slicing, copying, membership in lists, or repeated sorting inside the loop can invalidate the intended complexity.
Prevent it: Count every slice, copy, sort, membership check, and container update before claiming O(n log k).
Avoid
import heapq
def merge_sorted_rows(rows):
h=[(row[0],i,0) for i,row in enumerate(rows)]
heapq.heapify(h)
return [heapq.heappop(h)[0] for _ in range(len(h))]Use instead
import heapq
def merge_sorted_rows(rows):
heap = []
for row_index, row in enumerate(rows):
if row:
heapq.heappush(heap, (row[0], row_index, 0))
merged = []
while heap:
value, row_index, element_index = heapq.heappop(heap)
merged.append(value)
next_index = element_index + 1
if next_index < len(rows[row_index]):
heapq.heappush(heap, (rows[row_index][next_index], row_index, next_index))
return mergedWhere you will hit this: Kth Smallest in a Sorted Matrix(opens in a new tab)
Reviewed References
Official Python documentation supports language behavior. Canonical problem pages provide additional practice context.
- Python heapq — Heap Queue Algorithm(opens in a new tab)
python-docs · checked 2026-07-27