Skip to main content
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...