Back to ChallengesMerge K Sorted ArraysHard 45 min

Merge K Sorted Arrays

You are given a 2D array representing K sorted arrays. Your task is to merge them into a single sorted array. (Note: this is identical in implementation to the External Sorting simulation problem).

Examples

Input: arrays = [[1,2,3], [4,5,6], [7,8,9]]

Output: [1,2,3,4,5,6,7,8,9]

Merging sequential sorted arrays.

Constraints

• 1 <= arrays.length <= 10^4
• 1 <= arrays[i].length <= 500

Complexity Analysis

Time

O(N log K)

where N is total elements, K is number of arrays.

Space

O(N)

memory for the new arrays.

Test Cases

#1 Sequential arrays

Input: arrays = [[1,2,3], [4,5,6], [7,8,9]]

Expected: [1,2,3,4,5,6,7,8,9]

#2 Overlapping arrays

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

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

JavaScript

Output

Click "Run Code" to see output here...