Merge K Sorted Arrays
You get a list arrays. Each item in it is an array of integers that is already sorted from smallest to largest.
Combine all of them into one array that is sorted from smallest to largest, and return it.
- Keep every value. If a value appears more than once (in one array or in several arrays), it appears that many times in the result.
- Some inner arrays can be empty. If every inner array is empty, return an empty array.
Hint
Joining everything and sorting again works, but it does not use the fact that each array is already sorted. Look at the first unused value of every array. The smallest of those values is the next value of the answer. A min-heap (priority queue) gives you that smallest value quickly. With N values in total and k arrays, this takes O(N log k) time.
Examples
Example 1
- Input:
- [[2,6,9],[1,6,10],[3,4]]
- Output:
- [1,2,3,4,6,6,9,10]
All eight values are kept. The value 6 is in two arrays, so it appears twice in the result.
Example 2
- Input:
- [[],[-5,0],[]]
- Output:
- [-5,0]
Empty arrays add nothing. Only the middle array has values.
Example 3
- Input:
- [[],[]]
- Output:
- []
Every array is empty, so the result is an empty array.
Constraints
1 <= arrays.length <= 80 <= arrays[i].length <= 8-100 <= arrays[i][j] <= 100- Each
arrays[i]is sorted in non-decreasing order.
Run checks your code against the 3 examples. Submit checks it against all 163 tests and needs a free account. You can also try ideas in the free JavaScript or Python compiler.