HeapProblem 6 of 18Important
Merge K sorted arrays [IMP]
Problem Statement
Given K sorted arrays, merge them into a single sorted array.
Example:
- Input:
arr = [[1, 4, 7], [2, 5, 8], [3, 6, 9]] - Output:
[1, 2, 3, 4, 5, 6, 7, 8, 9] - Explanation: All three sorted arrays are merged into one sorted array.
Approach 1: Merge All and Sort (Brute Force)
Intuition
Concatenate all arrays into one and sort the result.
Algorithm
- Copy all elements from K arrays into a single array
- Sort the combined array
java
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
public class Solution {
public List<Integer> mergeKArrays(int[][] arrays) {
List<Integer> result = new ArrayList<>();
// Concatenate all arrays
for (int[] arr : arrays) {
for (int num : arr) {
result.add(num);
}
}
// Sort the result
Collections.sort(result);
return result;
}
}Complexity Analysis
- Time Complexity: O(NK log(NK)) - Where N is average array size, K is number of arrays
- Space Complexity: O(N*K) - For storing all elements
Approach 2: Merge Two at a Time
Intuition
Repeatedly merge two sorted arrays until only one remains.
Algorithm
- Take first two arrays and merge them
- Merge result with third array
- Continue until all arrays are merged
java
import java.util.ArrayList;
import java.util.List;
public class Solution {
private List<Integer> mergeTwoArrays(List<Integer> arr1, List<Integer> arr2) {
List<Integer> result = new ArrayList<>();
int i = 0, j = 0;
while (i < arr1.size() && j < arr2.size()) {
if (arr1.get(i) <= arr2.get(j)) {
result.add(arr1.get(i++));
} else {
result.add(arr2.get(j++));
}
}
while (i < arr1.size()) result.add(arr1.get(i++));
while (j < arr2.size()) result.add(arr2.get(j++));
return result;
}
public List<Integer> mergeKArrays(int[][] arrays) {
if (arrays.length == 0) return new ArrayList<>();
List<Integer> result = new ArrayList<>();
for (int num : arrays[0]) {
result.add(num);
}
for (int i = 1; i < arrays.length; i++) {
List<Integer> curr = new ArrayList<>();
for (int num : arrays[i]) {
curr.add(num);
}
result = mergeTwoArrays(result, curr);
}
return result;
}
}Complexity Analysis
- Time Complexity: O(N*K²) - Each merge takes O(current length) and we do K-1 merges
- Space Complexity: O(N*K) - For intermediate results
Approach 3: Divide and Conquer
Intuition
Pair up arrays and merge them, then merge the results. Like merge sort, but on arrays.
Algorithm
- Pair up K arrays and merge each pair
- Repeat until only one array remains
- Total log K levels of merging
java
import java.util.ArrayList;
import java.util.List;
public class Solution {
private List<Integer> mergeTwoArrays(List<Integer> arr1, List<Integer> arr2) {
List<Integer> result = new ArrayList<>();
int i = 0, j = 0;
while (i < arr1.size() && j < arr2.size()) {
if (arr1.get(i) <= arr2.get(j)) {
result.add(arr1.get(i++));
} else {
result.add(arr2.get(j++));
}
}
while (i < arr1.size()) result.add(arr1.get(i++));
while (j < arr2.size()) result.add(arr2.get(j++));
return result;
}
private List<Integer> mergeKArraysHelper(int[][] arrays, int left, int right) {
if (left == right) {
List<Integer> result = new ArrayList<>();
for (int num : arrays[left]) {
result.add(num);
}
return result;
}
if (left > right) {
return new ArrayList<>();
}
int mid = left + (right - left) / 2;
List<Integer> leftMerged = mergeKArraysHelper(arrays, left, mid);
List<Integer> rightMerged = mergeKArraysHelper(arrays, mid + 1, right);
return mergeTwoArrays(leftMerged, rightMerged);
}
public List<Integer> mergeKArrays(int[][] arrays) {
if (arrays.length == 0) return new ArrayList<>();
return mergeKArraysHelper(arrays, 0, arrays.length - 1);
}
}Complexity Analysis
- Time Complexity: O(NK log K) - log K levels, each level processes all NK elements
- Space Complexity: O(N*K log K) - For recursive calls and intermediate arrays
Approach 4: Min-Heap (Optimal)
Intuition
Use a min-heap to track the smallest element among the current elements from each array. Each element is processed exactly once.
Algorithm
- Create min-heap with first element of each array (along with array index and element index)
- Extract minimum, add to result
- Push next element from same array (if exists)
- Repeat until heap is empty
java
import java.util.PriorityQueue;
import java.util.ArrayList;
import java.util.List;
public class Solution {
public List<Integer> mergeKArrays(int[][] arrays) {
List<Integer> result = new ArrayList<>();
// Min-heap: {value, arrayIndex, elementIndex}
PriorityQueue<int[]> minHeap = new PriorityQueue<>(
(a, b) -> a[0] - b[0]
);
// Initialize with first element of each array
for (int i = 0; i < arrays.length; i++) {
if (arrays[i].length > 0) {
minHeap.offer(new int[]{arrays[i][0], i, 0});
}
}
// Extract min and add next element from same array
while (!minHeap.isEmpty()) {
int[] curr = minHeap.poll();
int value = curr[0];
int arrIdx = curr[1];
int elemIdx = curr[2];
result.add(value);
// If there are more elements in this array
if (elemIdx + 1 < arrays[arrIdx].length) {
minHeap.offer(new int[]{
arrays[arrIdx][elemIdx + 1],
arrIdx,
elemIdx + 1
});
}
}
return result;
}
}Complexity Analysis
- Time Complexity: O(NK log K) - Each of NK elements is pushed/popped once, heap has at most K elements
- Space Complexity: O(K) - Heap stores at most K elements (one from each array)
Key Takeaways
- Brute force ignores the sorted property completely
- Sequential merging is inefficient - O(N*K²) due to repeated work
- Divide and conquer is efficient - O(N*K log K) like merge sort
- Min-heap is optimal for space - only O(K) extra space
- Heap approach processes each element exactly once with O(log K) per operation
- This is a fundamental technique used in external sorting and database joins
- Same approach works for merging K sorted linked lists