CODEWITHSUNDEEP
arraysalgorithmsorting
Shyna
Shyna

Reputation: 145

Algorithm: How to Sort elements of matrix with space constraint

I am trying to understand the best possible way to solve this based on the constraints that are given. We have a matrix of numbers where each row is sorted. Our result should list all these elements in sorted order.

Example: 

Input:  
20  40  80  
5   60  90  
45  50  55     
output:
5 20 40 45 50 55 60 80 90

Constraint : You are only allowed to hold 1 row at a time
Possible Solutions:
1) Use array, put all elements in array and sort them -> o(n) space for array and o(n log n) time for sorting. But this used extra memory so the constraint is really not getting fulfilled.

2) Use priority queue. Put all elements in priority queue and remove to get elements in sorted order. Again this uses o(n) space but we have better time complexity i.e. o(log n)

I am not able to understand the fact that how we can solve it with given constraint. Can someone please advise if I am missing something. It looks difficult to solve it with the given constraint.

Upvotes: 0

Views: 200

Answers (1)

BufBills
BufBills

Reputation: 8103

Use a priority queue. The size of this queue should be size of rows you have. Then, insert fist elements from each row firstly. Secondly, retrieve min value from priority queue, then insert a new element from the same line that the element you just retrieved comes from. Thirdly, keep doing this, you get your result.

This does have a caveat though. Your constraint is keep space with in size of column. here I use space of size of row. But I think this is fair.

Think about this, if you have 2 columns and 1M rows, using an array with size 2 won't help at all.

Upvotes: 3

Related Questions