Median in a row-wise sorted Matrix

JavaView on GFG

Problem Overview

Find median of matrix where each row is sorted.

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?