HardPro challengePythonJavaScriptTypeScript
Sorting — Merge K Sorted Lists
AlgorithmsSortingMerge SortDivide and Conquer
solve(lists) — lists is an array of k arrays, each sorted ascending (some may be
empty). Return one sorted array holding every value. With N values in total the
target is O(N log k), not O(N · k) and not a final sort() of everything.
Two classic ways: a min-heap holding one candidate per list, or divide and conquer:
merge the lists two by two (reusing the merge step from Merge Sorted Array), halving the
number of lists each round.
Examples
solve([[1,4,5],[1,3,4],[2,6]]) → [1,1,2,3,4,4,5,6]
solve([[],[]]) → []
solve([[1],[0]]) → [0,1]Sample tests
Test #1Three lists
Input: [[[1,4,5],[1,3,4],[2,6]]]
Output: [1,1,2,3,4,4,5,6]
Test #2All lists empty
Input: [[[],[]]]
Output: []
Test #3Two single-value lists
Input: [[[1],[0]]]
Output: [0,1]