Matrix Median

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.

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

Approach 1

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.

Try Problem

Approach 2

The basic idea of this approach is to utilize the fact that elements in the row are stored in a sorted manner.

Suppose we want to create a sorted (in non-decreasing order) list of integers from the given matrix. Now let’s try to append the integers in the list one by one. Consider the first element of each row; the minimum of those elements will be the minimum element of the matrix itself. Why? Because the first element of each row is the minimum element of that row.

Now, to find the second smallest element, we will remove the smallest element, and we will consider the next element (2nd element) of the row where the minimum element was found. Following the steps mentioned above, we can easily find the sorted list of integers.

The above image explains the first five steps of the algorithm. The highlighted element is the minimum element of the matrix in each step. We can observe that we just need to consider elements of the first column to find the minimum. Therefore, we can use a min-heap data structure to operate efficiently.

Since the median is always the middle element in the sorted list, we simply do the above operation for ('N' * 'M')/2 times. And then the next smallest element will be the median.

The steps are as follows:

Create a min-heap which stores a pair <X, <'ROW', 'COL'> >, where ‘X’ is the element of the given matrix and <'ROW', 'COL'> is the index of that element in the matrix. The reason behind storing the index of that element is after removal of that element we will have to consider the next element from the same row for finding the next smallest element.
Initialize a 'COUNT' variable to zero which stores the number of elements that were removed from the min-heap.
Extract the minimum element from the min-heap and increment the 'COUNT'.
If 'COUNT' is ('N' * 'M') / 2 + 1, the current minimum element is the overall median of the matrix. Else,
Using the index of the minimum element, find the next element in that row and insert the pair of the next element and its index in the min-heap.
If that row doesn’t have any more elements, repeat the same process(from step 3).

Try Problem

Approach 3

The core idea of this approach is to utilize the property of the median and the sorted rows. Note that for a given list of integers whose length is 'N' * 'M', the median is the smallest number that is greater than or equal to at least ('N' * 'M')/2 elements in the list.

Let ‘X’ be the potential median of the matrix. Now, 'X’ can be any number from the matrix. We can do a binary search to find the ‘X’.

Let MIN and MAX be the minimum and maximum elements of the matrix, respectively. ‘X’ can be any number in the range of [MIN, MAX].
Initialize “LOW” and “HIGH” for the binary search algorithm to MIN and 'MAX, respectively. In other words, initialize our search space to [MIN, MAX].
We will iterate until “LOW” is not equal to “HIGH”
Initialize “MID” as (“LOW” + “HIGH”)/2.
Now, our task is to find the number of elements in the matrix that are less than or equal to the “MID” (say it is “count”).
Iterate through each row one by one.
- Since each row is sorted in non-decreasing order, we can easily find the total number of elements in that row that are less than or equal to “MID” using the upper_bound().
- Take the sum of such elements over each row.
- Now, if “count” is less than or equal to ('N' * 'M')/2 then, the median will be undoubtedly greater than mid. Therefore, change our search space to [“MID” + 1, “HIGH”], i.e. assign “MID” + 1 to “LOW”.
- Else, the median will indeed lie in the range of [“LOW”, “MID”], i.e. assign “MID” to “HIGH”.
Repeat this process while our search space doesn’t converge to a single element.
Since the steps mentioned above will terminate when “LOW” is equal to “HIGH”, we’ll get the overall median of the matrix which is “LOW”.

Try Problem