Print Matrix Elements In Sorted Order

Easy
0/40
Average time to solve is 15m
profile
Contributed by
4 upvotes
Asked in companies
AmazonFactSetNagarro Software

Problem statement

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.

Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1 :
2
1 3
1 2 3
2 3
2 6 9
1 5 11
Sample Output 1 :
1 2 3
1 2 5 6 9 11
Explanation For Sample Input 1 :
In the first test case, the list of the elements of the given matrix in a non-decreasing order is [1, 2, 3].

In the second test case, the list of the elements of the given matrix in a non-decreasing order is [1, 2, 5, 6, 9, 11].
Sample Input 2 :
2
3 3
2 6 8
1 4 7
6 8 9
2 2
4 6
1 2
Sample Output 2 :
1 2 4 6 6 7 8 8 9
1 2 4 6
Explanation For Sample Input 2 :
In the first test case, the list of the elements of the given matrix in a non-decreasing order is [1, 2, 4, 6, 6, 7, 8, 8, 9].

In the second test case, the list of the elements of the given matrix in a non-decreasing order is [1, 2, 4, 6].
Hint

Can you think of sorting the whole matrix?

Approaches (3)
Naive Approach

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:

  1. Create an auxiliary array/list of N*M length.
  2. Traverse the matrix and insert all the elements in that array/list.
  3. Sort that list/array in non-decreasing order.
Time Complexity

O( (N*M) * log(N*M ), where ‘N’ is the number of rows and ‘M’ is the number of columns in the given matrix.

 

Since we are sorting a list/array of integers whose length is N*M, so the overall complexity will be O( (N*M) * log(N*M )).

Space Complexity

O(N * M), where ‘N’ is the number of rows, and ‘M’ is the number of columns in the given matrix.

 

The only extra space which we are using is to store the elements of the matrix which are N*M in total. Therefore, the overall space complexity will be O(N*M).

Code Solution
(100% EXP penalty)
Print Matrix Elements In Sorted Order
Full screen
Console