Merge K Sorted Lists 30 XP Hard

LeetCode Ctrl+Enter Run Ctrl+S Save

Merge k sorted linked lists into one sorted list. This is a classic problem that combines heaps with linked lists.

# Input: [[1,4,5], [1,3,4], [2,6]]
# Output: [1, 1, 2, 3, 4, 4, 5, 6]
#
# The heap always gives us the smallest current element across all k lists

Min-heap approach — always grab the smallest available element:

Push the first element from each list into a min-heap
Pop the smallest from the heap → add to result
Push the next element from that same list into the heap
Repeat until heap is empty

Time: O(N log k) where N = total elements, k = number of lists. The heap never holds more than k elements, so each push/pop is O(log k). This is the technique used in external sorting for massive datasets!

📋 Instructions

Implement `merge_k_sorted(lists)` using a min-heap. Use simple lists (not linked lists) for simplicity. Test with the example above.

Push (value, list_index, element_index) to the heap. Pop smallest, add to result. If that list has more elements, push the next one. The tuple comparison handles ordering.

🧪 Test Cases

Input

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

Expected

[1, 1, 2, 3, 4, 4, 5, 6]

Test case 1

Input

merge_k_sorted([[], [1]])

Expected

[1]

Test case 2

← Previous Next Exercise →

main.py

Hi! I'm Rex 👋

Output

Ready. Press ▶ Run or Ctrl+Enter.

›