Coding Interview PatternsMerge K Sorted Lists
HardK-way Merge
Merge K Sorted Lists
Explanation & Solution
Description
You are given an array of k sorted linked lists. Merge all the linked lists into one sorted list and return it.
Input: lists = [[1,4,5],[1,3,4],[2,6]]
Output:[1,1,2,3,4,4,5,6]
0
1
1
1
2
2
3
3
4
4
5
4
6
5
7
6
Explanation: The three sorted lists merge into one sorted list.
Constraints
k == lists.length0 <= k <= 10^40 <= lists[i].length <= 500-10^4 <= lists[i][j] <= 10^4lists[i]is sorted in ascending order.
Approach
K-way Merge pattern
1. Seed the Min-Heap
- Push the first element of each non-empty list into a min-heap as
[value, listIndex, elementIndex] - This gives us k candidates — one from each list
2. Heapify
- Run
siftDownfrom the last internal node upward to establish the heap property in O(k)
3. Extract Minimum and Advance
- Repeatedly pop the root (global minimum) and append its value to
result - If the same list has a next element, replace the root with that element and sift down
- If the list is exhausted, remove the root by swapping with the last element and sifting down
4. Repeat Until Empty
- Continue until the heap is empty — at that point all elements have been merged
Key Insight
- The heap always holds exactly one element per active list, maintaining the invariant that the root is the current global minimum
Time
O(N log k) where N is total elements and k is the number of lists — each of N extractions costs O(log k)Space
O(k) for the heap