K-way Merge Pattern

K-way Merge Animation

K Sorted Lists (K = 3):

List 0:

List 1:

List 2:

Min Heap (size = 0):

Empty (All merged!)

Merged Result:

Empty (Starting...)

Start: We have 3 sorted lists. Use min heap to merge efficiently!

Speed:

Step 1 of 11

🎯 Explain Like I'm 5...

Imagine you and 2 friends each have a pile of numbered cards 🎴 (already in order!). You want to combine them into ONE big sorted pile!

🃏 Three Piles:

• Your pile: 1, 4, 7 (smallest on top!)
• Friend 1's pile: 2, 5, 8
• Friend 2's pile: 3, 6, 9

🎯 The Merging Game:

• Everyone shows their TOP card: 1, 2, 3
• Pick the SMALLEST (1)! Put it in the new pile!
• You flip your next card (4). Now tops are: 4, 2, 3
• Pick smallest (2)! Friend 1 flips next card...
• Keep going until ALL cards are in one pile!

Final pile: 1, 2, 3, 4, 5, 6, 7, 8, 9 - Perfect order! 🎉

🚀 The Magic: Use a special helper (min heap) that ALWAYS knows which card is smallest among all the tops! Instead of checking 3 piles each time, the helper just tells you "pick THIS one!" Super fast! ⚡

When Should You Use This Pattern?

✓Merging K sorted arrays/lists
✓Finding the smallest range covering elements from K lists
✓Finding the Kth smallest element in K sorted arrays
✓Problems with multiple sorted inputs

📝 Example 1: Merge K Sorted Lists

Merge K sorted linked lists into one sorted linked list.

Step-by-Step Thinking:

Add the first node of each list to a min heap
Pop smallest node from heap and add to result
Add the next node from that list to heap
Repeat until all nodes are processed

MergeKLists.java

java

import java.util.*;
class ListNode {
    int val;
    ListNode next;
    ListNode(int x) { val = x; }
}
public class MergeKLists {
    public static ListNode mergeKLists(ListNode[] lists) {
        if (lists == null || lists.length == 0) {
            return null;
        }
        // Min heap to track smallest node from each list
        PriorityQueue<ListNode> minHeap =
            new PriorityQueue<>((a, b) -> a.val - b.val);
        // Add first node of each list to heap
        for (ListNode node : lists) {
            if (node != null) {
                minHeap.offer(node);
            }
        }
        // Build result list
        ListNode dummy = new ListNode(0);
        ListNode current = dummy;
        while (!minHeap.isEmpty()) {
            // Get smallest node
            ListNode smallest = minHeap.poll();
            current.next = smallest;
            current = current.next;
            // Add next node from that list
            if (smallest.next != null) {
                minHeap.offer(smallest.next);
            }
        }
        return dummy.next;
    }
    public static void printList(ListNode head) {
        while (head != null) {
            System.out.print(head.val);
            if (head.next != null) System.out.print(" -> ");
            head = head.next;
        }
        System.out.println();
    }
    public static void main(String[] args) {
        // List 1: 1 -> 4 -> 5
        ListNode l1 = new ListNode(1);
        l1.next = new ListNode(4);
        l1.next.next = new ListNode(5);
        // List 2: 1 -> 3 -> 4
        ListNode l2 = new ListNode(1);
        l2.next = new ListNode(3);
        l2.next.next = new ListNode(4);
        // List 3: 2 -> 6
        ListNode l3 = new ListNode(2);
        l3.next = new ListNode(6);
        ListNode[] lists = {l1, l2, l3};
        ListNode result = mergeKLists(lists);
        System.out.print("Merged list: ");
        printList(result);
        // Output: 1 -> 1 -> 2 -> 3 -> 4 -> 4 -> 5 -> 6
    }
}

📝 Example 2: Kth Smallest in Sorted Matrix

Find the Kth smallest element in an n×n matrix where each row and column is sorted.

KthSmallestMatrix.java

java

import java.util.*;
public class KthSmallestMatrix {
    static class Element {
        int val;
        int row;
        int col;
        Element(int val, int row, int col) {
            this.val = val;
            this.row = row;
            this.col = col;
        }
    }
    public static int kthSmallest(int[][] matrix, int k) {
        int n = matrix.length;
        // Min heap to track smallest elements
        PriorityQueue<Element> minHeap =
            new PriorityQueue<>((a, b) -> a.val - b.val);
        // Add first element of each row
        for (int i = 0; i < Math.min(n, k); i++) {
            minHeap.offer(new Element(matrix[i][0], i, 0));
        }
        // Extract k smallest elements
        Element element = null;
        for (int i = 0; i < k; i++) {
            element = minHeap.poll();
            // Add next element from same row
            if (element.col + 1 < n) {
                minHeap.offer(new Element(
                    matrix[element.row][element.col + 1],
                    element.row,
                    element.col + 1
                ));
            }
        }
        return element.val;
    }
    public static void main(String[] args) {
        int[][] matrix = {
            {1,  5,  9},
            {10, 11, 13},
            {12, 13, 15}
        };
        int k = 8;
        System.out.println("Kth smallest: " + kthSmallest(matrix, k));
        // Output: 13
        // Sorted: [1, 5, 9, 10, 11, 12, 13, 13, 15]
    }
}

📝 Example 3: Smallest Range Covering K Lists

Find the smallest range that includes at least one number from each of the K lists.

SmallestRange.java

java

import java.util.*;
public class SmallestRange {
    static class Element {
        int val;
        int listIndex;
        int elementIndex;
        Element(int val, int listIndex, int elementIndex) {
            this.val = val;
            this.listIndex = listIndex;
            this.elementIndex = elementIndex;
        }
    }
    public static int[] smallestRange(List<List<Integer>> lists) {
        // Min heap for smallest elements
        PriorityQueue<Element> minHeap =
            new PriorityQueue<>((a, b) -> a.val - b.val);
        int currentMax = Integer.MIN_VALUE;
        int rangeStart = 0;
        int rangeEnd = Integer.MAX_VALUE;
        // Add first element from each list
        for (int i = 0; i < lists.size(); i++) {
            int val = lists.get(i).get(0);
            minHeap.offer(new Element(val, i, 0));
            currentMax = Math.max(currentMax, val);
        }
        // Process elements
        while (minHeap.size() == lists.size()) {
            Element smallest = minHeap.poll();
            int currentMin = smallest.val;
            // Update range if smaller
            if (rangeEnd - rangeStart > currentMax - currentMin) {
                rangeStart = currentMin;
                rangeEnd = currentMax;
            }
            // Add next element from same list
            if (smallest.elementIndex + 1 < lists.get(smallest.listIndex).size()) {
                int nextVal = lists.get(smallest.listIndex).get(smallest.elementIndex + 1);
                minHeap.offer(new Element(nextVal, smallest.listIndex, smallest.elementIndex + 1));
                currentMax = Math.max(currentMax, nextVal);
            }
        }
        return new int[]{rangeStart, rangeEnd};
    }
    public static void main(String[] args) {
        List<List<Integer>> lists = Arrays.asList(
            Arrays.asList(4, 10, 15, 24, 26),
            Arrays.asList(0, 9, 12, 20),
            Arrays.asList(5, 18, 22, 30)
        );
        int[] range = smallestRange(lists);
        System.out.println("Smallest range: [" + range[0] + ", " + range[1] + "]");
        // Output: [20, 24]
        // Contains: 20 from list2, 24 from list1, 22 from list3
    }
}

🔑 Key Points to Remember

1️⃣Use min heap to efficiently track smallest element across K lists
2️⃣Store additional info in heap (which list, which index)
3️⃣Time Complexity: O(N log K) where N is total elements, K is lists
4️⃣Space Complexity: O(K) for the heap

💪 Practice Problems

• Merge Sorted Array
• Find Median from Data Stream
• Kth Smallest Number in M Sorted Lists
• Minimum Cost to Connect Ropes