Merge K Sorted Arrays
Partition Equal Subset Sum Algorithm (GFG)
Description
The Merge K Sorted Arrays problem is an intuitive problem based on Priority Queue where we have to merge k sorted arrays into one final sorted array.
Video Explanation
Problem Definition
Given:
- A 2D array of integers
arrof size .
Objective:
- Merge these arrays into 1 sorted array. Return the merged sorted array.
Algorithm Overview
- Min Heap Approach:
- Creating a
MinHeapand Insert thefirstelementof all the k arrays. - Remove the
top mostelement of Minheap andputit in the output array. - And insert the
nextelementfromthearray of removedelements. - To get the
resultthe step must continue until there is no element left in the MinHeap.
- Return
result, which is the final sorted array after merging k sorted arrays.
Time Complexity
- Time Complexity: , where insertion and deletion in a Min Heap requires log K time and for all elements it takes time
- Space Complexity: for the result array.
Solutions
- C++
- Java
- Python
- JavaScript
#include <vector>
using namespace std;
//User function Template for C++
class Solution
{
public:
class triplet{
public:
int val;
int arr;
int i_indx;
};
struct cmp{
bool operator()(triplet a , triplet b){
return (a.val > b.val);
}
};
//Function to merge k sorted arrays.
vector<int> mergeKArrays(vector<vector<int>> arr, int k)
{
//code here
priority_queue<triplet , vector<triplet> , cmp> pq_min;
for(int i = 0 ; i < k ; i++){
pq_min.push({arr[i][0] , i , 0});// pushing the first element of each array
//Heap Node => { element , array-number , indx of element in that array}
}
vector<int> ans;
while(ans.size() != k*k){
triplet f = pq_min.top();
pq_min.pop();
ans.push_back(f.val);
int arr_indx = f.arr , i = f.i_indx;
i = i+1;
if(i < arr[arr_indx].size()){
pq_min.push({arr[arr_indx][i] , arr_indx , i}); //Pushing the next of that array from which popped out elements belongs to
}
}
return ans;
}
};
import java.util.PriorityQueue;
class Solution {
static class Element {
int val, r, c;
Element(int val, int r, int c) {
this.val = val;
this.r = r;
this.c = c;
}
}
public static int[] mergeKArrays(int[][] arr, int K) {
PriorityQueue<Element> minHeap = new PriorityQueue<>((a, b) -> a.val - b.val);
int totalElements = 0;
for (int i = 0; i < K; i++) {
if (arr[i].length > 0) {
minHeap.add(new Element(arr[i][0], i, 0));
totalElements += arr[i].length;
}
}
int[] result = new int[totalElements];
int idx = 0;
while (!minHeap.isEmpty()) {
Element curr = minHeap.poll();
result[idx++] = curr.val;
if (curr.c + 1 < arr[curr.r].length) {
minHeap.add(new Element(arr[curr.r][curr.c + 1], curr.r, curr.c + 1));
}
}
return result;
}
}
import heapq
class Solution:
def mergeKArrays(self, arr: List[List[int]], K: int) -> List[int]:
min_heap = []
for i in range(K):
if arr[i]:
heapq.heappush(min_heap, (arr[i][0], i, 0))
result = []
while min_heap:
val, r, c = heapq.heappop(min_heap)
result.append(val)
if c + 1 < len(arr[r]):
heapq.heappush(min_heap, (arr[r][c + 1], r, c + 1))
return result
class MinHeap {
constructor() { this.heap = []; }
push(val) {
this.heap.push(val);
this._up(this.heap.length - 1);
}
pop() {
if (this.heap.length === 0) return null;
const top = this.heap[0];
const bottom = this.heap.pop();
if (this.heap.length > 0) {
this.heap[0] = bottom;
this._down(0);
}
return top;
}
_up(i) {
while (i > 0) {
const p = (i - 1) >> 1;
if (this.heap[i].val < this.heap[p].val) {
[this.heap[i], this.heap[p]] = [this.heap[p], this.heap[i]];
i = p;
} else break;
}
}
_down(i) {
const n = this.heap.length;
while ((i << 1) + 1 < n) {
let left = (i << 1) + 1, right = left + 1, smallest = i;
if (left < n && this.heap[left].val < this.heap[smallest].val) smallest = left;
if (right < n && this.heap[right].val < this.heap[smallest].val) smallest = right;
if (smallest !== i) {
[this.heap[i], this.heap[smallest]] = [this.heap[smallest], this.heap[i]];
i = smallest;
} else break;
}
}
}
var mergeKArrays = function(arr, K) {
const minHeap = new MinHeap();
for (let i = 0; i < K; i++) {
if (arr[i].length > 0) {
minHeap.push({ val: arr[i][0], r: i, c: 0 });
}
}
const result = [];
while (minHeap.heap.length > 0) {
const { val, r, c } = minHeap.pop();
result.push(val);
if (c + 1 < arr[r].length) {
minHeap.push({ val: arr[r][c + 1], r: r, c: c + 1 });
}
}
return result;
};
Track Your Progress
Done with this topic? Mark it as complete to track your progress.
Related Practice Problems
Handpicked problems sharing similar algorithmic topic tags
Hard
#Array#Sorting
Maximum Building Height
Finding the maximum possible height of a building given a set of restrictions using a two-pass constraint propagation approach.
Solve Problem→
Medium
#Array#Sorting
Destroying Asteroids
Finding if a planet can destroy all asteroids using a greedy approach.
Solve Problem→
Medium
#Array#Sorting
Maximum Ice Cream Bars
Finding the maximum number of ice cream bars that can be bought with a given amount of coins using a greedy approach.
Solve Problem→
💬 Discuss this page
Have a question or spot something confusing in "Merge K Sorted Arrays"? Ask below — it's backed by GitHub Discussions, so maintainers get notified like any other GitHub activity.