Last Updated: 15 Dec, 2020
Median In Matrix
Moderate
Asked in companies
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.
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
Approaches
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:
- Take an array of size N*M.
- Push all the elements of the input matrix in the array.
- Sort the array.
- Return the middle value of the sorted array.
Another simplest way to use a data structure which keeps its elements sorted, that is an ordered map. Insert all the elements of the given matrix in the map such that the key is the element and the corresponding value is the number of times the element occurs in the matrix. Iterate the map and return the middle element, that is the median.
Algorithm:
- Take an ordered map.
- Push all the elements of the input matrix in the map. .
- Return the middle value of the map.
The rows of the input matrix are sorted, so we can use this property of the matrix to solve the problem. Binary search works on sorted arrays and thus binary search can be used to find median in this case. The idea is that for a number to be median there should be exactly (N/2) elements that are less than it. So, find that number using binary search.
Algorithm:
- The first column will contain all the minimum values of all the rows and the last column will contain all the maximum values of all the rows. Find the minimum and maximum values of the input matrix using the first and the last column respectively.
- Use binary search on the range of numbers ranging from minimum and maximum values found in step 1. Find their middle value and find the count of numbers in the matrix which are less than the middle value, and accordingly change the values of maximum and minimum.
- For a number to be median, there should be (N*M)/2 numbers smaller than that number. So for every number, we get the count of numbers less than that in each row of the matrix. If the count is less than the required count, the median must be greater than the current selected value, else it must be lesser.
- Return the value of median.
Similar problems