Sorted Matrix

Posted: 22 Sep, 2020
Difficulty: Moderate

PROBLEM STATEMENT

Try Problem

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
Approach 1

We have a simple brute force solution for this problem.

 

  1. Initialize a list ‘ANS’ of size N * N to store the elements of the matrix in sorted order.
  2. Store all the elements of the matrix in the list ‘ANS’.
  3. Sort the elements of the list in ascending order.
  4. Return the ‘ANS’.
Try Problem