Merge K Sorted Lists

Combine multiple sorted lists into one sorted list efficiently.

merge sorting heap lists

Given a list of sorted lists (each sorted in non-decreasing order), implement a function `merge_k_sorted(lists)` that returns a new list containing all elements from all input lists, sorted in non-decreasing order. The input `lists` is a list of lists, possibly containing empty lists. The total number of elements across all lists is `N`. Aim for O(N log K) time, where K is the number of non-empty lists, and O(N) auxiliary space in the worst case.

Constraints

0 <= number of lists <= 10^4
0 <= length of each list <= 10^4
Total elements N <= 10^5
Elements are integers within the range [-10^9, 10^9]

Expected time complexity: O(N log K)
Expected space complexity: O(N) for the output (plus O(K) for the heap if you use one).

Example

>>> merge_k_sorted([[1, 4, 5], [1, 3, 4], [2, 6]])
[1, 1, 2, 3, 4, 4, 5, 6]
>>> merge_k_sorted([[], [1], [2, 3]])
[1, 2, 3]
>>> merge_k_sorted([])
[]

45 points ~40 min

Recent Submissions

No submissions yet — hit Run Tests to try!

Hints

Consider using a min-heap to always extract the smallest current head among all lists.

When you pop an element from the heap, push the next element from the same list into the heap.

Alternatively, you could use Python's `heapq.merge` as a shortcut, but implementing a manual heap-method deepens understanding.

Test Results

Press Ctrl+Enter or click Run Tests to execute your code.