Merge K sorted Arrays doubt1

#1

One test case is showing W.A. Please help.

#2

Hello @Rooopak_Sharma ,

Your code is not working for the testcases like:
2 4
1 6 7 8
5 2 3 4
Your Output:
1 5 2 6 3 7 4 8
Expected output:
1 2 3 4 5 6 7 8
This is happening because you are checking for elements columns-wise.

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

#3

But we have sorted arrays given and 5 2 3 4 is already not sorted.

#4

That’s a typing error:

Corrected example:
2 4
1 6 7 8
2 3 4 5
Your Output:
1 2 3 6 4 7 5 8

AS you can see, the error is same as what i have explained in my previous reply.

#5

Then what should be the correct approach to tackle this issue sir ?

#6

Hello @Rooopak_Sharma,

The simplest way of doing it is by using an output array/vector:

  1. copy all the elements from different sorted arrays to this output array.
  2. Sort the output array

This approach takes O(N Logn N) time where N is count of all elements.
Simple. But, isn’t it time inefficient?

Let’s look for an efficient approach then:
What data-structure can we use to sort sequence of elements efficiently?..
HEAP

  1. Create an output array.
  2. Create a min heap of size k and insert 1st element in all the arrays into the heap
  3. Repeat following steps while priority queue is not empty.
    ……a) Remove minimum element from heap (minimum is always at root) and store it in output array.
    ……b) Insert next element from the array from which the element is extracted. If the array doesn’t have any more elements, then do nothing.

The time complexity of heap based solution is O(N Log k).

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

#7

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.

#8

I don’t understand the reason behind this algorithm. Please explain with a example sir.

#9

Sure @Rooopak_Sharma,

What i have observed that in your code, you are using the logic specified for efficient approach.
But, that approach is not applicable for the testcase that i have specified.

So, now we are left with the simple approach:

start putting elements in the min priority queue from a[] array as:

for(i = 0; i < k; i++){
for ( j = 0 ; j < n ; ++j )
pq.push(a[i][j]);
}
these 4 lines have sorted your k lists.

Now to print them you just have to show top element and then pop it as:

for(i = 0; i < kn ; i++){ //Notice that i: 0 -> kn
cout << pq.top() << ’ ’ ;
pq.pop() ;
}

Hope, this helpful.
Give a like, if you are satisfied.