Last Updated: 22 Sep, 2020
Sorted Matrix
Moderate
Asked in companies
You are given an N x N matrix 'MAT' of positive integers, where every row and column is sorted in non-decreasing order.
Your task is to return a list containing all elements of the matrix in sorted order.
For example :
If the matrix is:
10 20 30 40
15 20 35 42
27 29 37 46
32 33 38 49
The output will be the elements of matrix in sorted order:
10 15 20 20 27 29 30 32 33 35 37 38 40 42 46 49
Follow Up:
Can you solve this in O((N ^ 2) * log(N)) time and O(N) space complexity?
Input format :
The first line of input contains a single integer T, representing the number of test cases or queries to be run.
Then the T test cases follow.
The first line of each test case contains a positive integer N, which represents the number of rows and columns in the matrix.
The next 'N' lines, each contains 'N' single space-separated positive integers representing the elements in a row of the matrix.
Output Format :
For each test case, print a single line containing the elements of the matrix in sorted order.
Note:
You do not need to print anything. It has already been taken care of. Just implement the given function.
Constraint :
1 <= T <= 10
1 <= N <= 100
1 <= MAT[i][j] <= 10^5
Time Limit: 1 sec
Approaches
We have a simple brute force solution for this problem.
- Initialize a list ‘ANS’ of size N * N to store the elements of the matrix in sorted order.
- Store all the elements of the matrix in the list ‘ANS’.
- Sort the elements of the list in ascending order.
- Return the ‘ANS’.
The idea is to use a Min Heap of size ‘N’ which stores elements of the first column. It extracts the minimum and replaces the minimum element with the next element of the row from which the element is extracted.
- Create a class Triplet whose data members would be the element, its row, and its column.
- Create a min-heap of type Triplet of size N and a list ‘ANS’ of size N*N to store the elements in sorted order.
- Store the elements of the first column in the heap along with their row and column numbers.
- Run a loop while the heap does not become empty.
- Extract the Triplet having minimum element value from the heap and store the element in the list ‘ANS’.
- Store the next element of the row from which the element is being extracted if it is not the last element of the row.
- Return the list ‘ANS’.