Last Updated: 17 Dec, 2020
Print Matrix Elements In Sorted Order
Easy
Asked in companies
You have been given a matrix of ‘N’ rows and ‘M’ columns filled up with integers where every row is sorted in non-decreasing order. Your task is to return all the elements of the given matrix in non-decreasing order.
Input Format :
The first line contains a single integer ‘T’ representing the number of test cases.
The first line of each test case will contain two integers ‘N’ and ‘M’ denoting the number of rows and columns, respectively.
Next ‘N’ lines contain ‘M’ space-separated integers each denoting the elements in the matrix.
Output Format :
For each test case, print N*M space-separated integers which denote the elements of the given matrix in non-decreasing order.
Output for every test case will be printed in a separate line.
Note :
You don’t need to print anything; It has already been taken care of.
Constraints:
1 <= T <= 50
1 <= N , M <= 10^2
0 <= matrix[i][j] <= 10^5
Where ‘T’ is the number of test cases.
Where 'N' is the number of rows in the given matrix, and 'M' is the number of columns in the given matrix.
And, matrix[i][j] denotes the value at (i, j)th cell in the matrix.
Time Limit: 1 sec
Approaches
The basic idea of this approach is to store the elements of the matrix in an array/list and then sort the elements. Steps are as follows:
- Create an auxiliary array/list of N*M length.
- Traverse the matrix and insert all the elements in that array/list.
- Sort that list/array in non-decreasing order.
The idea is based on the divide-and-conquer strategy. We take pairs of the sorted list at each step. Then merge the pairs using the two-pointer technique of merging two sorted arrays. Thus, after merging all the pairs, the number of arrays will reduce by half. We will continue this till the number of remaining arrays doesn’t become 1.
Now consider a recursive function that sorts the elements of given rows of the matrix in non-decreasing order and stores the result in the matrix itself, i.e. in place. In the resulting matrix, the elements of the rows will be in non-decreasing order, and also the first element of subsequent rows will be greater than the last element of the previous row.
sortRows(int low, int high, vector<vector<int>> &matrix) Where “low” and “high” denotes the index of the lower and higher row which needs to be sorted. Now consider the steps as follows:
- If “low” is equal to “high” then do nothing because a matrix with a single row is already sorted.
- Initialise a variable “mid” = (“low” + “high”)/2 which divides the matrix into two half, one consisting of rows [“low”, “mid”] and the other one [“mid” + 1, “high”]
- Recur for the left half, i.e. sortRows(“low, “mid”, matrix). This step will sort the rows
- Similarly, recur for the right half, i.e. sortRows(“mid” + 1, “high”, matrix)
- Now, we will use two pointer technique to merge the two sorted matrices.
We can store the elements of the matrix in an array/list which will be in sorted order.
The basic idea of this approach is to utilize the fact that elements in the row are stored in a sorted manner.
Suppose we want to create a sorted (in non-decreasing order) list of integers from the given matrix. Now let’s try to append the integers in the list one by one. Consider the first element of each row; the minimum of those elements will be the minimum element of the matrix itself. Why? Because the first element of each row is the minimum element of that row.
Now, to find the second smallest element, we will remove the smallest element, and we will consider the next element (2nd element) of the row where the minimum element was found. Following the steps mentioned above, we can easily find the sorted list of integers.
The above image explains the first five steps of the algorithm. The highlighted element is the minimum element of the matrix in each step. We can observe that we just need to consider elements of the first column to find the minimum. Therefore, we can use a min-heap data structure to operate efficiently.
Steps are as follows :
- Create a min-heap which stores a pair <x, <row, col> >, where ‘x’ is the element of the given matrix and <row, col> is the index of that element in the matrix. The reason behind storing the index of that element is after removal of that element we will have to consider the next element from the same row for finding the next smallest element.
- Initialise an array/list which stores the elements of the matrix in sorted order.
- Extract the minimum element from the min-heap and increment the “count”.
- Using the index of the minimum element, find the next element in that row and insert the pair of the next element and its index in the min-heap.
- If that row doesn’t have any more elements, repeat the same process(from step 3).