Merge K Sorted Streams
You receive lists, an array of sorted linked lists, each given as an array of numbers in ascending order. Think of them as sorted log streams from several servers.
Merge them into one sorted array and return it. Aim for O(N log k) time, where N is the total number of elements and k the number of lists.
Example 1
Input: lists = [[1,4,5],[1,3,4],[2,6]] Output: [1,1,2,3,4,4,5,6]
Example 2
Input: lists = [] Output: []
Constraints
- 0 <= k <= 10^4
- 0 <= lists[i].length <= 500
- Total elements <= 10^4
- Each list is sorted ascending.
Hint 1
Put the head of every list into a min-heap keyed by value.
Hint 2
Pop the smallest, append it, and push the next element from the same list.
Discussion 0
Join free to post in the discussion.
Good practice for: Backend Developer, Data Engineer, Database Administrator, Site Reliability Engineer, Cloud Engineer
Run checks your code on 3 sample tests. Submit runs all 7 tests, including hidden ones, and earns points. Use console.log to debug. Python's first run can take a few seconds while it starts.