Merge K Sorted Lists

Difficulty: Hard · Topic: Heaps

Given a list of sorted lists, merge them into one sorted list. Push the head of each list into a min-heap keyed by value; repeatedly pop the smallest and push the next element from the list it came from — O(N log k) for k lists and N total elements.

Examples

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

merge_k_sorted([[1],[0]])
→ [0,1]

Target complexity: time O(N log k), space O(k)

Write your solution in Python and run it against hidden tests right on this page. Progressive hints and Python + C++ reference solutions are included.

Learn the idea first: the lesson for this problem.