Merge K sorted Arrays

#1

Is this approach fine?
1.make heap insert element
2.make for loop and check minimum of 3 elements from starting i then from next pointer i +1 again 3 elements .
3. store minimum in another heap and print it.

#2

Hello @kunalsaini8950,

  1. Yes, it will work, considering that i is the index of that array in which the smallest element exists.
  2. Also, don’t fix the comparison elements to 3. Rather, the number of elements you should compare should be equal to the no. of sorted arrays.
    Reason:
    This way you can compare the current smallest element of each sorted array.

Your logic aligns with the logic explained in the video.
You, can also go through it, for a better understanding.

Hope, this would help.
Give a like if you are satisfied.

#3

Can you explain line 18 to 23 in detail ?

#4

Sure @kunalsaini8950,

while(!pq.empty())
{
//store the smallest element of the priority_queue
pp front=pq.top();

//delete that element from the priority_queue
pq.pop();

//Inserting the smallest element present in the priority_queue to the vector
oarr.push_back(front.first);

//id: represents the row of the smallest element.
int id=front.second.first;

//j: represents the column at which the smallest element is present in arr
int j=front.second.second;

//cheching if there is any element present at the right of the smallest element in the (id)th row.
//Alternative:
//if(j+1<n)
if(j+1<arr[id].size())
    //push the next element of (id)th row into the priority_queue
    pq.push({arr[id][j+1],{id,j+1}});

}

Let me know, if you still have any doubt.
Give a like if you are satisfied.

#5

deleted post x due to some reason

#6

Yes @kunalsaini8950,

If you want an example, then let me know.

#7

deleted post x due to some reason