Median of a Matrix with sorted rows

Question

I am not able to solve the following problem optimally nor finding an approach to do this anywhere.

Given a N × M matrix in which each row is sorted, find the overall median of the matrix. Assume N*M is odd.

For example,

Matrix =
[1, 3, 5]
[2, 6, 9]
[3, 6, 9]

A = [1, 2, 3, 3, 5, 6, 6, 9, 9]

Median is 5. So, we return 5.
Note: No extra memory is allowed.

Any help will be appreciated.

Answer 1

Consider the following process.

• If we consider the N*M matrix as 1-D array then the median is the element of 1+N*M/2 th element.

• Then consider x will be the median if x is an element of the matrix and number of matrix elements ≤ x equals 1 + N*M/2.

• As the matrix elements in each row are sorted then you can easily find the number of elements in each row less than or equals x. For finding in the whole matrix, the complexity is N*log M with binary search.

• Then first find the minimum and maximum element from the N*M matrix. Apply Binary Search on that range and run the above function for each x.

• If the number of elements in matrix ≤ x is 1 + N*M/2 and x contains in that matrix then x is the median.

You can consider this below C++ Code :

int median(vector<vector<int> > &A) {
    int min = A[0][0], max = A[0][0];
    int n = A.size(), m = A[0].size();
    for (int i = 0; i < n; ++i) {
        if (A[i][0] < min) min = A[i][0];
        if (A[i][m-1] > max) max = A[i][m-1];
    }

    int element = (n * m + 1) / 2;
    while (min < max) {
        int mid = min + (max - min) / 2;
        int cnt = 0;
        for (int i = 0; i < n; ++i)
            cnt += upper_bound(&A[i][0], &A[i][m], mid) - &A[i][0];
        if (cnt < element)
            min = mid + 1;
        else
            max = mid;
    }
    return min;
}

Answer 2

This Question is quite similar to finding kth smallest element in a row and column wise sorted matrix.

So this problem can be solved using binary search and optimised counting in a sorted Matrix. A binary search takes O(log(n)) time and for each search value it takes n iterations on average to find the numbers that are smaller than the searched number. The search space for binary search is limited to the minimum value in the Matrix at mat[0][0] and the maximum value mat[n-1][n-1].

For every number that is chosen from the binary search we need to count the numbers that are smaller than or equal to that particular number. And thus the k^th smallest number or the median can be found.

For better understanding you can refer to this video:

https://www.youtube.com/watch?v=G5wLN4UweAM&t=145s