← Back to Index

📚 K-Way Merge Pattern – Java Cheat Sheet

📌 About the Pattern

The K-Way Merge pattern helps efficiently merge K sorted lists (arrays or linked lists) into one sorted list. This generalizes the traditional 2-way merge (like in merge sort).

One popular approach uses a min-heap (priority queue):

1. Insert the first element of each list into a min heap.
2. Extract the smallest item from the heap and add it to the result list.
3. Insert the next element from the list the extracted item came from (if available).
4. Repeat until all elements are merged.

Use Case: Merging K sorted streams/logs, external sorting, median computation, etc.

🧱 Pattern Template

class Solution {
    public List<Integer> mergeKSortedLists(List<List<Integer>> lists) {
        PriorityQueue<int[]> minHeap = new PriorityQueue<>((a, b) -> a[0] - b[0]);
        List<Integer> result = new ArrayList<>();

        // Step 1: Add the first element of each list to the heap
        for (int i = 0; i < lists.size(); i++) {
            if (!lists.get(i).isEmpty()) {
                minHeap.offer(new int[]{lists.get(i).get(0), i, 0}); // [value, listIndex, elementIndex]
            }
        }

        // Step 2: Extract the smallest element and add the next element from the same list
        while (!minHeap.isEmpty()) {
            int[] smallest = minHeap.poll();
            result.add(smallest[0]);
            int listIndex = smallest[1];
            int elementIndex = smallest[2];

            // Add the next element from the same list to the heap
            if (elementIndex + 1 < lists.get(listIndex).size()) {
                minHeap.offer(new int[]{lists.get(listIndex).get(elementIndex + 1), listIndex, elementIndex + 1});
            }
        }

        return result;
    }
}

📊 Time Complexity

• Heap Initialization: O(K log K) – Adding the first element of each list to the heap.
• Heap Operations: O(N log K) – Extracting and adding elements to the heap, where N is the total number of elements across all lists.
• Overall Complexity: O(N log K).

✅ Use Cases

• Merging multiple sorted arrays or linked lists
• Efficiently combining sorted data streams
• Applications in external sorting and database systems

📘 Common LeetCode Problems

• 23. Merge k Sorted Lists [Hard] Heap [Cheat Sheet]
• 378. Kth Smallest Element in a Sorted Matrix [Medium] Heap [Cheat Sheet]
• 373. Find K Pairs with Smallest Sums [Medium] Heap [Cheat Sheet]
• 786. K-th Smallest Prime Fraction [Medium] Heap [Cheat Sheet]
• 313. Super Ugly Number [Medium] Heap [Cheat Sheet]
• 88. Merge Sorted Array [Easy] Two Pointers [Cheat Sheet]
• 668. Kth Smallest Number in Multiplication Table [Hard] Heap [Cheat Sheet]
• 632. Smallest Range Covering Elements from K Lists [Hard] Heap [Cheat Sheet]

🧪 Example: Merge K Sorted Lists

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

Explanation:
- Add the first element of each list to the heap: [1, 1, 2].
- Extract the smallest (1) and add the next element from the same list.
- Repeat until all elements are merged into the result list.

▶️ View Animation

💡 Pro Tips

• Use a min-heap to efficiently track the smallest element among the lists.
• Edge cases: empty lists, lists of unequal lengths.
• Ensure the heap stores enough information to track the source of each element.