881738. Merge Sorted Arrays Using Minheap
Merge Sorted Arrays Using Minheap
Slug: merge-sorted-arrays-using-minheap--114218
Difficulty: Easy
Topic Tags: STL
Company Tags: None
Summary
This problem requires merging two or more sorted arrays into a single sorted array. The approach involves using a min heap data structure to efficiently find and remove the smallest element from each array, effectively merging them in ascending order.
Detailed Explanation
The algorithm begins by initializing an empty min heap. Each of the input arrays is then iterated over, with each element being inserted into the min heap along with its corresponding array index. The min heap ensures that the smallest element (i.e., the root) is always the one to be extracted first.
To merge the arrays, we repeatedly extract the minimum element from the min heap and add it to the result array. We then insert the next element from each input array into the min heap along with its corresponding array index. This process continues until all elements have been processed, at which point the result array contains the merged sorted array.
Here is a step-by-step breakdown of the solution:
- Initialize an empty min heap.
- Iterate over each input array and insert each element into the min heap along with its corresponding array index.
- Repeatedly extract the minimum element from the min heap and add it to the result array.
- Insert the next element from each input array into the min heap along with its corresponding array index.
- Repeat steps 3-4 until all elements have been processed.
The time complexity of this algorithm is O(N log N), where N is the total number of elements across all arrays, due to the use of a min heap for efficient element extraction and insertion. The space complexity is O(1) since we only need to maintain the min heap and the result array, which have a constant maximum size.
Optimized Solutions
Java
import java.util.PriorityQueue;
public class MergeSortedArrays {
public static int[] merge(int[][] arrays) {
PriorityQueue<Integer> pq = new PriorityQueue<>();
for (int i = 0; i < arrays.length; i++) {
if (arrays[i].length > 0) {
pq.add(arrays[i][0]);
}
}
int[] result = new int[arrays[0].length];
int idx = 0;
while (!pq.isEmpty()) {
result[idx++] = pq.poll();
for (int i = 0; i < arrays.length; i++) {
if (arrays[i].length > 0) {
pq.add(arrays[i][0]);
arrays[i] = Arrays.copyOfRange(arrays[i], 1, arrays[i].length);
}
}
}
return result;
}
}