Matrix Median

Moderate
0/80
Average time to solve is 15m
96 upvotes
Asked in companies
AmazonIntuitCisco

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 find the overall median of the matrix i.e if all elements of the matrix are written in a single line, then you need to return the median of that linear array.

The median of a finite list of numbers is the "middle" number when those numbers are listed in order from smallest to greatest. If there is an odd number of observations, the middle one is picked. For example, consider the list of numbers [1, 3, 3, 6, 7, 8, 9]. This list contains seven numbers. The median is the fourth of them, which is 6.

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 an integer which is the overall median of the given matrix.

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. Just implement the given function.
Constraints:
1 <= 'T' <= 50
1 <= 'N' , 'M' <= 100
1 <= 'MATRIX'['I']['J'] <= 10 ^ 5
'N' * 'M' is always an odd number.

Where '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
3 3
2 6 9
1 5 11
3 7 8
Sample Output 1:
2
6
Explanation of sample input 1:
In the first test case, the overall median of the matrix is 2.

In the second test case, the overall median of the matrix is 6.
Sample Input 2:
2
3 3
2 6 8
1 4 7
6 8 9
3 5
1 2 6 6 10
2 4 4 5 7
2 5 5 6 6
Sample Output 2:
2
5
Explanation for sample input 2:
In the first test case, the overall median of the matrix is 2.

In the second test case, the overall median of the matrix is 5.
Hint

Can you think of sorting the whole matrix?

Approaches (3)
Naive Approach

Since, the median is the middle number in a sorted, ascending or descending, list of numbers, our basic idea is to generate the list of integers from the given matrix in a sorted manner. The 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 element on the (('N' * ‘M’)/2)th index (0-based indexing) will be the overall median of the matrix.
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).

Video Solution
Unlock at level 3
(75% EXP penalty)
Code Solution
(100% EXP penalty)
Matrix Median
Full screen
Console