Pattern Guide
K-Way Merge
"Merge k sorted structures with a min-heap. Find smallest range, kth smallest."
K-way merge combines k sorted arrays/lists into a single sorted stream. Core tool: min-heap storing the current minimum from each of the k lists. Each step: extract minimum from heap, advance that list's pointer, push next element. Applications: merge k sorted lists, find k-th smallest in sorted matrix, smallest range covering k lists, external merge sort.
Problems you can solve with this pattern
4 problems · click any to start solving
// Merge k sorted arrays using min-heap
// Simulating with sorted array (in practice use a proper heap)
function mergeKSortedArrays(arrays) {
const heap = []; // [value, arrayIdx, elemIdx]
// Initialize heap with first element of each array
for (let i = 0; i < arrays.length; i++)
if (arrays[i].length) heap.push([arrays[i][0], i, 0]);
heap.sort((a, b) => a[0] - b[0]);
const result = [];
while (heap.length) {
heap.sort((a, b) => a[0] - b[0]); // maintain heap property
const [val, ai, ei] = heap.shift();
result.push(val);
if (ei + 1 < arrays[ai].length)
heap.push([arrays[ai][ei+1], ai, ei+1]);
}
return result;
}K-way merge: min-heap of size k stores (value, list_index, element_index). Pop min, add to result, push next element from same list. O(n log k) total where n = total elements. Kth smallest in sorted matrix: same idea — treat each row as a sorted list. Smallest range: maintain window [min, max] while advancing the list that had the minimum.
// Merge k sorted arrays using min-heap
// Simulating with sorted array (in practice use a proper heap)
function mergeKSortedArrays(arrays) {
const heap = []; // [value, arrayIdx, elemIdx]
// Initialize heap with first element of each array
for (let i = 0; i < arrays.length; i++)
if (arrays[i].length) heap.push([arrays[i][0], i, 0]);
heap.sort((a, b) => a[0] - b[0]);
const result = [];
while (heap.length) {
heap.sort((a, b) => a[0] - b[0]); // maintain heap property
const [val, ai, ei] = heap.shift();
result.push(val);
if (ei + 1 < arrays[ai].length)
heap.push([arrays[ai][ei+1], ai, ei+1]);
}
return result;
}Pattern variations:
- Merge k lists: same pattern, pointer follows linked list next
- Kth smallest in matrix: binary search on value (more elegant than heap)
- Smallest range: maintain max separately, advance min's list
- K pairs smallest sum: expand one dimension at a time
Lazy deletion heap: For priority queues where elements become invalid, push (priority, id) to heap. When popping, check if id is still valid; skip if not. Avoids O(n) removal from heap.