Median of a Matrix with sorted rows

A simple O(1) memory solution is to check if each individual element z is the median. To do this we find the position of z in all rows, just accumulating the number of elements smaller than z. This doesn't use the fact that each row is sorted except finding the position of z in each row in O(log M) time. For each element we need to do N*log M comparisons, and there are N*M elements, so it is N²M log M.

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

If the matrix elements are integers, one can binary search the median starting with the matrix range for hi and low. O(n log m log(hi-low)).

Otherwise, one way that has O(n²log²m) wost-case time complexity is to binary search, O(log m), for each row in turn, O(n), the closest element to the overall matrix median from the left and the closest from the right, O(n log m), updating the best so far. We know the overall median has no more than floor(m * n / 2) elements strictly less than it, and that adding the number of elements less than it and the number of times it occurs can be no less than floor(m * n / 2) + 1. We use standard binary search on the row, and – as greybeard pointed out – skip the test for elements outside our 'best' range. The test for how close an element is to the overall median involves counting how many elements in each row are strictly less than it and how many equal, which is achieved in O(n log m) time with n binary searches. Since the row is sorted, we know greater elements would be more "to the right" and lesser elements more "to the left" in relation to the overall median.

If one is permitted to rearrange the matrix, O(mn log (mn)) time complexity is possible by sorting the matrix in place (using block sort, for example) and returning the middle element.

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