Last Updated: 1 Feb, 2021

Median in a row-wise sorted Matrix

Moderate

Asked in companies

Solve now

Problem statement

You are given a row-wise sorted matrix 'mat' of size m x n where 'm' and 'n' are the numbers of rows and columns of the matrix, respectively.

Your task is to find and return the median of the matrix.

Note:

'm' and 'n' will always be odd.

Example:

Input: 'n' = 5, 'm' = 5
'mat' = 
[     [ 1, 5, 7, 9, 11 ],
      [ 2, 3, 4, 8, 9 ],
      [ 4, 11, 14, 19, 20 ],
      [ 6, 10, 22, 99, 100 ],
      [ 7, 15, 17, 24, 28 ]   ]

Output: 10

Explanation: If we arrange the elements of the matrix in the sorted order in an array, they will be like this-

1 2 3 4 4 5 6 7 7 8 9 9 10 11 11 14 15 17 19 20 22 24 28 99 100 

So the median is 10, which is at index 12, which is midway as the total elements are 25, so the 12th index is exactly midway. Therefore, the answer will be 10.

Input format :

The first line contains two space-separated integers, 'm', and 'n', representing the number of rows and the columns of the matrix, respectively.

Each of the next 'm' lines contains 'n' space-separated integers denoting the elements of the matrix.

Output format :

Return a single integer representing the median of the matrix.

Note:

You don’t have to print anything; it has already been taken care of. Just implement the given function.

Solve now

Approaches

01 Approach

The idea is that we would spread out the whole matrix and store it in an array and after that we would sort that array and check the middle of the array.

Declare an array ‘spreadMatrix’ to store the elements of the matrix.
Iterate through the matrix and push each element of it onto the array ‘spreadMatrix’.
Sort the array ‘spreadMatrix’.
Return the middle element that is spreadMatrix[(M * N)/2];

Solve now

02 Approach

The idea is that, for a number to be the median of the matrix the number should be exactly greater than half the numbers in the matrix. Therefore, we will find the count of numbers less than each number, and the element which satisfies the above property will be the median.

We will find a range of the numbers to be checked for the count and the range will be the minimum and the maximum number of the matrix.
Minimum and maximum numbers in the matrix can be found by comparing numbers in the starting and the last column of the matrix.
Then we will apply Binary Search over the range of minimum and maximum numbers obtained above.
Run a while loop until the minimum number is less than the maximum and continuously update accordingly.
- We define the mid of these two extremes that are mid of the minimum and the maximum.
- Calculate the count of numbers that are less than this number, mid.
- As stated above for a number to be the median of the array the number should be exactly greater than half the numbers in the matrix.
- If the count of the numbers less than ‘mid’ is less than half of the numbers in the matrix then the median will obviously be greater than this number so we update the minimum number to be mid + 1.
- Otherwise, if the count is greater, we update the maximum to mid because it will lie in the first half.
Finally, return the minimum number after all this process.

Solve now