Merge K Sorted Arrays
Mahabharata — The Grand Unification — Merging k Armies into One Sorted Formation
k क्रमबद्ध सेनाओं को एक में — लघु-ढेर से। प्रत्येक सेना का अगला — ढेर में प्रतीक्षा करे॥
*Merge k sorted armies into one — via min-heap. Each army's next warrior — awaits in the heap.*
The Story
Given k sorted arrays, merge them into one sorted array.
For `arr=[[1,2,3],[4,5,6],[7,8,9]]`: result=[1,2,3,4,5,6,7,8,9]. For `arr=[[1,3,5,7],[2,4,6,8],[0,9,10,11]]`: result=[0,1,2,3,4,5,6,7,8,9,10,11].
**Min-Heap as Pointer:** - Initialize: add the first element of each array to the min-heap as (value, arrayIndex, elementIndex) - Repeat: poll the minimum → add to result → push the next element from that same array
```java PriorityQueue<int[]> pq = new PriorityQueue<>((a,b)->a[0]-b[0]); // Min by value for (int i=0; i<arr.length; i++) pq.offer(new int[]{arr[i][0], i, 0}); // (value, array_i, element_j)
ArrayList<Integer> result = new ArrayList<>(); while (!pq.isEmpty()) { int[] top = pq.poll(); result.add(top[0]); int ai=top[1], ei=top[2]; if (ei+1 < arr[ai].length) pq.offer(new int[]{arr[ai][ei+1], ai, ei+1}); } ```
The heap always maintains the 'current front' of each array. The minimum of these fronts is the next element in the merged result.
Trace `[[1,3],[2,4],[0,5]]`: - Init: pq=[(0,2,0),(1,0,0),(2,1,0)] - Poll (0): result=[0], push (5,2,1): pq=[(1,0,0),(2,1,0),(5,2,1)] - Poll (1): result=[0,1], push (3,0,1): pq=[(2,1,0),(3,0,1),(5,2,1)] - Poll (2): result=[0,1,2], push (4,1,1): pq=[(3,0,1),(4,1,1),(5,2,1)] - Poll (3): result=[0,1,2,3], no next in arr[0]: pq=[(4,1,1),(5,2,1)] - Poll (4,5): result=[0,1,2,3,4,5] ✓
The Flatten and Sort Approach
Add all elements to one list, sort it. O(n log n) where n = total elements.
public ArrayList<Integer> mergeKArraysBruteForce(int[][] arr) {
ArrayList<Integer> result = new ArrayList<>();
for (int[] a : arr) for (int v : a) result.add(v);
Collections.sort(result);
return result;
}The K-Front Min-Heap Wisdom
public static ArrayList<Integer> mergeKArrays(int[][] arr) {
PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[0] - b[0]);
for (int i = 0; i < arr.length; i++)
pq.offer(new int[]{arr[i][0], i, 0});
ArrayList<Integer> result = new ArrayList<>();
while (!pq.isEmpty()) {
int[] top = pq.poll();
result.add(top[0]);
int ai = top[1], ei = top[2];
if (ei + 1 < arr[ai].length)
pq.offer(new int[]{arr[ai][ei + 1], ai, ei + 1});
}
return result;
}Step-by-Step Walkthrough
[[5]], k=1 Init: pq=[(5,0,0)] Poll: result=[5], no next. Return [5] ✅
Deep Insight
**Why O(n log k)?** n = total elements. Each element is inserted and extracted from the heap once. Heap size is at most k (one per array). Each insert/extract is O(log k). Total: O(n log k).
**The pattern 'Heap as Pointer':** The heap doesn't store data — it stores pointers (arrayIndex, elementIndex) into the arrays. This is a powerful pattern: instead of copying data into the heap, you store navigational references.
**Same pattern in hp-9:** Kth smallest in sorted matrix using this heap-as-pointer approach.
**Merge k Sorted Linked Lists:** Same algorithm, just with ListNode pointers instead of (ai, ei) indices.
Complexity Analysis
| Approach | Time | Space | Note |
|---|---|---|---|
| Brute Force | O(n log n) | O(n) | Collect all + sort |
| Optimal | O(n log k) | O(k) | Heap of k pointers, n operations |
Pattern Recognition
✅ Merge k sorted → min-heap of k pointers ✅ Store (value, arrayIdx, elemIdx) in heap ✅ Poll min → push next from same array ✅ Heap size stays ≤ k throughout **LeetCode Trigger Phrases:** → "merge k sorted arrays" / "merge k sorted lists" → Heap-as-pointer pattern → Multi-way merge
Bhagavad Gita 6.31
सर्वभूतस्थितं यो मां भजत्येकत्वमास्थितः। सर्वथा वर्तमानोऽपि स योगी मयि वर्तते॥
The yogi who, established in unity, worships Me dwelling in all beings — in whatever circumstances, that yogi abides in Me.
Connection: K separate sorted armies, each with their own sequence, are unified into one harmonious formation. The min-heap finds unity by always identifying who comes next across all k fronts simultaneously. Like the yogi who sees the divine dwelling in all beings — one consciousness behind many forms — the algorithm sees the true next element across k separate arrays and weaves them into a single unified sequence.