Sorted Matrix

Moderate

0/80

Average time to solve is 25m

40 upvotes

Asked in companies

Problem statement

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?

Detailed explanation ( Input/output format, Notes, Images )

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

Sample Input 1 :

1
4
10 20 30 40
15 20 35 42
27 29 37 46
32 33 38 49

Sample Output 1:

10 15 20 20 27 29 30 32 33 35 37 38 40 42 46 49

Explanation for Input 1:

After sorting all the elements of the matrix in increasing order, we will get 10 15 20 20 27 29 30 32 33 35 37 38 40 42 46 49.

Sample Input 2 :

Sample Output 2:

1 2 5 6

Hint 1

Think of storing all the elements in the list and sort them.

Approaches (2)

Approach 1

Approach 2

Brute Force

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’.

Time Complexity

O(N ^ 2 * log(N ^ 2)), where N is the number of rows in the matrix.

We are storing all the elements in the list. The number of elements that get added to the list will be N * N. Thus time complexity to sort them will be O(N ^ 2 * log(N ^ 2)).

Space Complexity

O(1).

Constant space is used.

(100% EXP penalty)

Sorted Matrix

Console