Merge K Sorted Arrays

Heapshard

Given `lists`, an array of individually sorted (ascending) integer arrays, implement `mergeKSorted(lists)` returning one sorted array containing all the elements. Use a min-heap for an O(N log k) merge.

Examples

Input: [[1, 4, 5], [1, 3, 4], [2, 6]]

Output: [1, 1, 2, 3, 4, 4, 5, 6]

Input: [[], [1]]

Output: [1]

Sample tests

Input: mergeKSorted([[1,4,5],[1,3,4],[2,6]])

Output: [1,1,2,3,4,4,5,6]

Input: mergeKSorted([[],[1]])

Output: [1]

+ 2 hidden tests run on Submit.

Hints

Common pitfalls

Concatenating then sorting is O(N log N) and ignores that the inputs are already sorted.
Pushing the next element from the wrong list breaks the merge — carry the list index with each heap entry.

Learning resources

Wikipedia: Binary heap

Approach & explanation (try first)

The heap always holds at most one candidate per list — the current frontier — so its smallest entry is the next element of the merged output. Each of the N elements is pushed and popped once, each operation O(log k). O(N log k) time.

⌘/Ctrl + Enter

Run your code to see results.

← Back to problems

Merge K Sorted Arrays

Heapshard

Examples

Input: [[1, 4, 5], [1, 3, 4], [2, 6]]

Output: [1, 1, 2, 3, 4, 4, 5, 6]

Input: [[], [1]]

Output: [1]

Sample tests

Input: mergeKSorted([[1,4,5],[1,3,4],[2,6]])

Output: [1,1,2,3,4,4,5,6]

Input: mergeKSorted([[],[1]])

Output: [1]

+ 2 hidden tests run on Submit.

Hints

Common pitfalls

Concatenating then sorting is O(N log N) and ignores that the inputs are already sorted.
Pushing the next element from the wrong list breaks the merge — carry the list index with each heap entry.

Learning resources

Wikipedia: Binary heap

Approach & explanation (try first)

⌘/Ctrl + Enter

Run your code to see results.