algorithm - 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;
}