Merge K sorted arrays

Medium

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: []

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
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;
}