Median In Matrix

Moderate
0/80
Average time to solve is 25m
profile
Contributed by
31 upvotes
Asked in companies
AdobeThought WorksReverie Language Technologies

Problem statement

Given a row-wise sorted matrix having N number of rows and M number of columns. Your task is to find the median of the given matrix.

Note :

Assume that the size of the matrix N*M is always odd.
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 two space separated integers N & M, the number of rows and columns respectively.

The next N lines of each test case contains M single space separated integers each, representing the elements of the matrix.

Output Format :

For each test case, print an integer denoting the median of the matrix.

The output of each test case is printed in a separate line.

Note :

You do not need to print anything, it has already taken care of. Just implement the given function.

Constraints :

1 <= T <= 10
1 <= N,M <= 10^4
-10^8 <= matrix[i][j] <= 10^8

Where 'matrix[i][j]' is the value of the element at 'jth' column of 'ith' row of the matrix.

Time Limit: 1 sec

Sample Input 1 :

1
3 3 
1 3 5
2 6 9
3 6 9

Sample Output 1 :

5
Explanation for Sample Input 1 :
On sorting the input matrix
1 2 3 3 5 6 6 9 9
The median of the above sorted array is its middle value and that is 5.

Sample Input 2 :

2
1 1 
5
1 3
1 4 6

Sample Output 2 :

5
4
Hint

Sort the above matrix and make a 1D array.

Approaches (3)
Naive approach

The simplest way to find the median of the input matrix is to convert it into a 1D sorted array. Take an array of size N*M and push all the elements of the input matrix in the array. Sort the array and return the middle value, that is the median.

 

Algorithm:

  1. Take an array of size N*M.
  2. Push all the elements of the input matrix in the array.
  3. Sort the array.
  4. Return the middle value of the sorted array.
Time Complexity

O((N*M)*(log(N*M))), where N & M are the number of rows and columns of the input matrix respectively.

 

All the elements of the input matrix are pushed in an array taking O(N*M) time. The algorithm uses an inbuilt sorting algorithm to sort the array of size R*C. So, for sorting time complexity will be O((N*M)*(log(N*M))). So, the final time complexity of the algorithm is O(N*M) + O(N*M*(log(N*M))) = O(N*M*(log(N*M))).

Space Complexity

O(N*M),  where N & M are the number of rows and columns of the input matrix respectively.

 

An array of size N*M is required to store the elements of the input matrix.

Code Solution
(100% EXP penalty)
Median In Matrix
Full screen
Console