Merge K sorted arrays
Problem
Given k sorted arrays, return one sorted array containing all their elements. Aim for O(N log k), where N is the total number of elements.
Example 1
Input: [[1, 3, 5, 7], [2, 4, 6, 8], [0, 9, 10, 11]] Output: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]
Also asked as: Merge “K” sorted arrays
Test cases
Case 1
Input: [[1,3,5,7],[2,4,6,8],[0,9,10,11]] Expected: [0,1,2,3,4,5,6,7,8,9,10,11]
Case 2
Input: [[1,1],[1]] Expected: [1,1,1]
Case 3
Input: [[1],[],[0]] Expected: [0,1]
Case 4
Input: [[]] Expected: []
View solutionHide solution1 approach
1. Min-heap of (value, arrayIdx, elemIdx)
Time O(N log K)Space O(K)
Seed with the first element of each array; pop the smallest, output it, push the next element from the same array.
function mergeKArrays(arrays) { const heap = arrays.map((arr, i) => [arr[0], i, 0]).filter((x) => x[0] !== undefined); heap.sort((a, b) => a[0] - b[0]); const out = []; while (heap.length) { const [val, ai, ei] = heap.shift(); out.push(val); if (ei + 1 < arrays[ai].length) { const next = [arrays[ai][ei + 1], ai, ei + 1]; let i = heap.findIndex((x) => x[0] > next[0]); i === -1 ? heap.push(next) : heap.splice(i, 0, next); } } return out;}