Pattern Reference
K-Way Merge
"Merge k-sorted arrays/lists, smallest range covering k lists, merge k-sorted iterators."
Loading...
Deep Dive Tutorial
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.
K-way merge with min-heap simulation
// 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;
}Worked Problems
shuffle
K-way merge complexity: O(n log k) where n = total elements, k = number of lists. Min-heap of size k enables O(log k) extraction and insertion.
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.
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.