Median in a row-wise sorted Matrix

JavaView on GFG

Intuition

Find median of matrix where each row is sorted. Binary search on value, count elements <= mid.

Algorithm

1Binary search on value range [min, max]. Count elements <= mid using binary search on each row. Find smallest value with count > m*n/2.

Common Pitfalls

•O(r * log(max-min) * log(c)). Counting elements <= x across sorted rows uses binary search per row.

Median in a row-wise sorted Matrix.java

Java

// Approach: Binary search on value. Count elements <= mid across all rows (each with binary search). Check if count = n*m/2+1.
// Time: O(n * log(max) * log(m)) Space: O(1)
class Solution {
    public int median(int[][] mat) {
        int n = mat.length;
        int m = mat[0].length;
        int med = (n * m) / 2 + 1;
        int[] counter = new int[2001];
        for (int i = 0; i < mat.length; i++) {
            for (int j = 0; j < mat[0].length; j++) {
                counter[mat[i][j]]++;
            }
        }

        int total = 0;
        for (int i = 1; i < 2001; i++) {
            total += counter[i];
            if (total >= med)
                return i;
        }
        
        return -1;
    }
}

Was this solution helpful?