394. Merge K Sorted Lists (Optimal — Min Heap)

Given k sorted linked lists, merge them into a single sorted list using a min-heap for optimal O(N log k) time. Each list is given as a sorted array; return the merged list as an array. Input: a JSON array of arrays.

Input: JSON array of sorted arrays.

Output: Array — the merged sorted list.

Examples

Input: [[1,4,5],[1,3,4],[2,6]]
Output: [1,1,2,3,4,4,5,6]
Explanation: Optimal k-way merge.

Input: [[]]
Output: []
Explanation: Empty.

Input: [[1]]
Output: [1]
Explanation: Single list.

Constraints

• 0<=k<=10^4
• total nodes<=10^5

Asked by