Median of Row-wise Sorted Matrix

Problem Statement: Median of Row-wise Sorted Matrix

We are given a row-wise sorted matrix of size r*c, we need to find the median of the matrix given. It is assumed that r*c is always odd.

Examples:

1 3 5

2 6 9

3 6 9

Output : Median is 5

We have presented two approaches to solve the problem:

Approach 1: Brute Force

The very first approach that comes to our mind is to store all the elements of the given matrix in an array of size r * c. Then we can either sort the array and find the median element in O(r*clog(r*c)). But since it is not the efficent one so we need to think of more optimised solution.

Approach 2 Efficient: Using Binary Search

The idea here is to leverage the binary search algorithm in order to optimize this problem. If you have paid attention to the definition of median, you must have noticed in case of odd elements the median is (1+N*M)/2 th smallest number which basically implies that (1+N*M)/2 is the total number of elements which are smaller or equal to our median.One more thing to analyse is, the median will always lie in the range of minimum and maximum element.Using these observations and applying binary search for elements in the above range (minimum, maximum) and maintaing the counter for smaller or equal numbers for each element in this range, we can find our median(discussed above based on count of smaller or equal elements).

Let us see a step-by-step approach to this solution:

1. First, we need to find the minimum and maximum elements from the matrix. The minimum and maximum can be easily found since the rows are sorted so we need to comapare with the first element of each row for minimum and last element of each row for maximum.

2. After finding our min and max, we can apply binary search on this range. The mid element can be calculated and number of elements smaller or equal to mid can be calculated, we have used upper_bound() function for this.

3.Based on the value of our counter, the min and max can be adjusted accordingly based on what we do for binary search.

#include<bits/stdc++.h>
using namespace std;
#define c 3
#define r 3
int findMedian(int mat[][c]) {
   int smallest = INT_MAX, largest = INT_MIN;
   for (int i=0; i<r; i++) {
      if (mat[i][0] < smallest)
         smallest = mat[i][0];
      if (mat[i][c-1] > largest)
         largest = mat[i][c-1];
   }
   while (smallest < largest){
      int mid = smallest + (largest - smallest) / 2;
      int smallCount = 0;
      for (int i = 0; i < r; ++i)
         smallCount += upper_bound(mat[i], mat[i]+c, mid) -
      mat[i];
      if (smallCount < ( (r * c + 1) / 2 ))
         smallest = mid + 1;
      else
         largest = mid;
   }
   return smallest;
}
int main(){
   int mat[][c]= { {2, 5, 7}, {4, 6, 8}, {1, 8, 9} };
   cout<<"The median of the matrix is "<<findMedian(mat);
   return 0;
}

def matrix_median(matrix):
    def find_less_than_x(x):
        lesser = 0
        for i in range(m):
            l, h = 0, n - 1
            while l <= h:
                mid = (l + h) // 2
                if matrix[i][mid] <= x:    l = mid + 1
                else:    h = mid - 1
            lesser += l
        return lesser
    m, n = len(matrix), len(matrix[0])
    low, high = 1, 10 ** 9
    median_idx = (m * n) // 2
    while low <= high:
        x = (low + high) // 2
        val = find_less_than_x(x)
        if val <= median_idx:    low = x + 1
        else:    high = x - 1
    return low

if __name__=='__main__':
    matrix = [[1, 3, 5],
              [2, 6, 9],
              [3, 6, 9]]
    print(matrix_median(matrix))

Time Complexity: O(N*logM)

Space Complexity: O(1)