Practise Link: https://practice.geeksforgeeks.org/problems/merge-k-sorted-arrays/1
Given K sorted arrays arranged in the form of a matrix of size K*K. The task is to merge them into one sorted array.
Thq question is looking for a sorted unidirectional array,from a 2d matrix which is already sorted in some special manner. We could have used sorting algorithm, the time and space complexity would be O(nlogn) and O(n^2) where n=k. We used heap in order to save the space however time comeplxity remains the same. Here are the steps that i used
- Push all the first col elements in the priority queue with the row and column number, here we are using a min heap
- After that, run a while loop with a condition that the heap is not empty
- In the while loop pop out the top element from the heap, get the row and col num , check if the col_num is the last colum or not
- If col_num is the last column number i.e. k-1, then repeatedly pop the elements from the heap, until col_num is the last column.
- When the program comes out of the while loop, check that still the col_num is the last column or not.
- If it is not then push the element present at the row_num and col_num +1 in the heap.
- When popping the element from the heap, add the item in the output list.
Here is the working code.
class Item{
int row_num;
int col_num;
int value;
Item(){
}
Item(int row_num,int col_num,int value){
this.row_num = row_num;
this.col_num = col_num;
this.value = value;
}
}
class Solution
{
//Function to merge k sorted arrays.
public static ArrayList<Integer> mergeKArrays(int[][] arr,int k)
{
// Write your code here.
PriorityQueue<Item> pq = new PriorityQueue<Item>(new Comparator<Item>(){
public int compare(Item i1,Item i2){
return i1.value-i2.value;
}
});
for(int i=0;i<k;i++){
pq.add(new Item(i,0,arr[i][0]));
}
ArrayList<Integer> op = new ArrayList<Integer>();
while(!pq.isEmpty()){
Item item = pq.poll();
int row_num = item.row_num;
int col_num = item.col_num;
op.add(item.value);
while(!pq.isEmpty()&&col_num==k-1){
item = pq.poll();
row_num = item.row_num;
col_num = item.col_num;
op.add(item.value);
}
if(col_num !=k-1){
pq.add(new Item(row_num,col_num+1,arr[row_num][col_num+1]));
}
}
return op;
}
}