🔀

K-Way Merge — Min-Heap on Heads

Push the head of each sorted list into a min-heap. Always poll() the global minimum → append to result → push its next node into the heap. Repeat until heap is empty.

🏔️ Min-Heap on Heads ⚡ O(n log k) 🔗 K Sorted Lists Time O(n log k) Space O(k)

📋 When to Use

Merge K sorted linked lists — classic problem, O(n log k)
K sorted arrays — same pattern, track (val, arrayIdx, elemIdx)
Push one head per list — heap size = K at all times
Poll min → result; push next from same list (if exists)
Kth smallest in sorted matrix — treat rows as K sorted lists

💡 Key insight: the heap always holds exactly K candidates (one per list). You only need to compare K numbers at a time, never all n. This gives O(log K) per operation vs O(K) for naive approach.

⚡ Complexity

Time

O(n log k)

Space

O(k)

n = total nodes across all K lists. Each node: one offer + one poll = O(log K).
Heap holds at most K nodes at any time → O(K) space.
Compare: merge two-at-a-time = O(n log k) but O(n) space.
Naive (compare all K heads) = O(nK) — much worse for large K.

Problem Given K = 3 sorted linked lists, merge them into one sorted list. Push each list's head into a min-heap. Always poll the global minimum, append to result, then push its next node. Each poll is O(log K) — total O(n log K) for n elements across K lists.
Input: L1 = [1,4,7], L2 = [2,5,8], L3 = [3,6,9] · Answer: [1,2,3,4,5,6,7,8,9]

Step 0 / 11

🔄 Init 🚀 Push Heads ⬇️ Poll Min ⬆️ Push Next ✅ Complete

Heap Size0

Operations0

Result Length0

📋 Input Lists (sorted)

🔵 L1

🟢 L2

🟣 L3

🏔️ Min-Heap (current heads) ⬇️ min = next to merge

Push heads to initialize…

📤 Merged Result

—

🔀 K-Way Merge: Push the head of each sorted list into a min-heap. Always poll the global minimum, then push the next node from that list. O(n log K) for n total nodes across K lists.

PriorityQueue<ListNode> pq = new PriorityQueue<>((a,b) -> a.val - b.val);

🧩 Pattern Skeleton Java 8

// K-Way Merge — min-heap holds current heads ─────────────────
PriorityQueue<ListNode> pq = new PriorityQueue<>(
    (a, b) -> a.val - b.val);         // min-heap by value

for (ListNode list : lists)           // push head of each list
    if (list != null) pq.offer(list);

ListNode dummy = new ListNode(0), curr = dummy;
while (!pq.isEmpty()) {
    ListNode node = pq.poll();        // global minimum
    curr.next = node;
    curr = curr.next;
    if (node.next != null)            // push next from same list
        pq.offer(node.next);
}
return dummy.next;

// For sorted arrays: track (value, arrayIdx, elemIdx)
PriorityQueue<int[]> pq2 = new PriorityQueue<>((a,b) -> a[0]-b[0]);

🎯 Practice Problems

#23Merge K Sorted Lists 🔀 min-heap headsHard #378Kth Smallest Element in Sorted Matrix 🔢 K-way on rowsMedium #373Find K Pairs with Smallest Sums 🔢 K-way on pairsMedium #632Smallest Range Covering K Lists 📏 K-way + range trackingHard #264Ugly Number II 🔢 3-way merge ×2 ×3 ×5Medium