Amazon — Merge K Sorted Lists (Min-Heap)

Problem Statement#

Given an array of k linked lists where each list is sorted in ascending order, merge all lists into one sorted linked list and return it.

Constraints:

• k == lists.length
• 0 <= k <= 10^4
• 0 <= lists[i].length <= 500
• -10^4 <= lists[i][j] <= 10^4
• Total nodes N <= 10^4

Input:  lists = [[1,4,5],[1,3,4],[2,6]]
Output: [1,1,2,3,4,4,5,6]

Input:  lists = []
Output: []

Why This Problem Matters#

Merge K Sorted Lists (LeetCode 23) is Amazon's most-asked hard problem across all interview stages. It directly models external merge sort — the algorithm behind Amazon Redshift, S3 Select, and any distributed database that merges sorted partitions from multiple nodes. When Amazon's MapReduce framework aggregates sorted outputs from hundreds of worker nodes, it performs exactly this operation.

Naive concatenation and sort costs O(N log N). The divide-and-conquer merge (pair up lists, merge pairs) costs O(N log k). The min-heap approach also costs O(N log k) but is more intuitive to implement correctly in an interview. Both are expected to be known.

The key skill being tested: you must efficiently find the minimum across k candidates at every step. A min-heap provides this in O(log k) per extraction, making the total O(N log k) instead of O(N * k) for naive selection.

The Core Insight#

Maintain a min-heap initialized with the head of each non-empty list. Each heap entry is (node.val, index, node) where index breaks ties (Python's tuple comparison would fail on ListNode objects). Repeatedly pop the minimum, add it to the result, and push that node's next (if it exists).

This always selects the globally smallest remaining node in O(log k) per step. Since there are N total nodes, total time is O(N log k).

Visual Dry Run#

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

Solution (Optimal)#

import heapq
 
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
 
class Solution:
    def mergeKLists(self, lists: list) -> ListNode:
        heap = []
        for i, node in enumerate(lists):
            if node:
                heapq.heappush(heap, (node.val, i, node))
 
        dummy = ListNode(0)
        curr = dummy
 
        while heap:
            val, i, node = heapq.heappop(heap)
            curr.next = node
            curr = curr.next
            if node.next:
                heapq.heappush(heap, (node.next.val, i, node.next))
 
        return dummy.next

var mergeKLists = function(lists) {
    // Min-heap via sorted array for simplicity; replace with real heap for large k
    const dummy = { val: 0, next: null };
    let curr = dummy;
 
    // Collect all nodes, sort, and relink
    const nodes = [];
    for (const head of lists) {
        let node = head;
        while (node) {
            nodes.push(node.val);
            node = node.next;
        }
    }
    nodes.sort((a, b) => a - b);
 
    for (const val of nodes) {
        curr.next = { val, next: null };
        curr = curr.next;
    }
    return dummy.next;
};
 
// Optimal heap-based version requires a priority queue implementation
// Use the Python version's logic with a MinHeap class (see KthLargest post)

Time: O(N log k) — N total nodes, each extracted/inserted into heap of size k Space: O(k) — heap holds at most k nodes at once

Common Mistakes#

• Pushing ListNode objects directly into Python's heap — comparison fails when values are equal
• Using i (list index) as the tie-breaker to avoid comparing ListNode objects
• Not filtering out null heads when initializing the heap
• Forgetting to push node.next after popping node
• Using divide-and-conquer but implementing the base case incorrectly for empty lists

Interview Tips#

• Immediately state the time complexity: O(N log k) with a heap vs O(N*k) naive
• The tuple (val, index, node) trick is Python-specific — explain why index is needed (tie-breaking)
• Mention the divide-and-conquer alternative: merge pairs of lists log(k) times, each O(N)
• Draw the heap state for the first 3 steps — shows clear understanding of the data flow
• Amazon sometimes asks you to merge k sorted arrays instead of linked lists — same approach, index into array instead

Follow-up Questions#

• How do you merge k sorted arrays instead of linked lists? — Same heap; push (val, list_idx, element_idx)
• What if k is very large (millions of lists)? — External merge sort with disk-based heaps
• What is the divide-and-conquer approach? — Merge pairs: O(N log k) time with O(log k) recursion stack
• How do you merge k sorted streams in real-time? — Same heap; push next element when current is consumed
• What if lists are not fully in memory? — Read one element at a time from each; heap handles the rest

Key Takeaways#

• A min-heap of size k allows O(log k) minimum extraction vs O(k) linear scan — the key improvement
• Total time is O(N log k): N nodes each processed once, heap operations cost O(log k)
• Always use a tuple (val, tie_breaker, node) in Python to avoid ListNode comparison errors
• The dummy head node pattern eliminates edge cases for list construction
• Amazon tests this as a proxy for distributed merge sort — a real system-at-scale operation
• Both heap and divide-and-conquer achieve O(N log k); the heap is simpler to code under interview pressure
• This pattern generalizes to any k-way merge: sorted files, database partitions, or log streams