Median in a row-wise sorted Matrix
Tags: geeksforgeeks, algorithms, dsa, beginners
Published: 2022-11-01 18:02:30

Given a row-wise sorted matrix of size R*C where R and C are always odd, find the median of the matrix.

> Problem link: https://practice.geeksforgeeks.org/problems/median-in-a-row-wise-sorted-matrix1527/1

Example 1:
```
Input:
R = 3, C = 3
M = [[1, 3, 5], 
     [2, 6, 9], 
     [3, 6, 9]]
Output: 5
Explanation: Sorting matrix elements gives 
us {1,2,3,3,5,6,6,9,9}. Hence, 5 is median. 
```

Example 2:
```
Input:
R = 3, C = 1
M = [[1], [2], [3]]
Output: 2
Explanation: Sorting matrix elements gives 
us {1,2,3}. Hence, 2 is median.
```

> ##### Expected Time Complexity: O(32 * R * log(C))
> ##### Expected Auxiliary Space: O(1)

## Solution

Let's dig down earlier on wtf is the median.
So, **in an odd** quantity array *(`means array.length % 2 == 1`)*, a median is the middle element when the array is fully sorted.

That means, in the sorted form of an array if the definite number *(`array.length/2`)* elements are ahead of a number then that number would be called the median. 

Here as well we get row wise sorted Matrix, where each row is sorted in ascending order.

We first assume a median, by taking the average of the minimum and maximum of the entire matrix.
Thereon we consider each row of the matrix, along with the assumed median. With this, we come to know for a row how many elements are present in front of the assumed median. This should be done on every row.

After performing this operation on each row we get the exact number of elements before the assumed median.

Rest is simple.
If the number of elements before the assumed median is much more than the calculation then,
*the actual median should be lesser than the assumed median*
else 
*the actual median should be greater than the assumed median*

Likewise, alter the assumed median until the point we get the assumed median to be actual.
Altering of assumed median could be done by altering the minimum and maximum variables, as the assumed mean is just the average of those two.

Here's the self-explanatory code:

```
class Solution {
    int median(int a[][], int R, int C) {
        int min = a[0][0]; // the left most boundary
        int max = a[0][C-1]; // the right most boundary
        final int aptPosition = (R*C+1) / 2;
        
        // these min max are for specific row
        // let get min max for all the rows
        
        for(int currentRow = 0; currentRow < R; currentRow++) {
            min = Math.min(min, a[currentRow][0]);
            max = Math.max(max, a[currentRow][C-1]);
        }
        
        // now we have globally min and max
        while(min < max) {
            int passedElement = 0;
            int assumedMedian = min + (max - min) / 2;

            for (int currentRow = 0; currentRow < R; currentRow++)
                passedElement += getElementPassed(a[currentRow], assumedMedian);

            if (passedElement < aptPosition)
                min = assumedMedian + 1;
            else 
                max = assumedMedian;
        }
        return min;
    }
    
    int getElementPassed(int[] a, int x) {
        int index = Arrays.binarySearch(a, x);
        if (index < 0)
            return -index - 1;
        while(index < a.length && a[index] == x)
            index++;
        return index;
    }
}
```