Median in a Row Wise Sorted Matrix | Binary Search on Answer

Problem Statement

Given a row-wise sorted matrix of size N × M, find the median of the matrix.

The matrix contains an odd number of elements.

Brute Force Intuition

In an interview, you can explain it like this:

Since every row is sorted, one straightforward approach is to collect all elements into a single array, sort them, and return the middle element. This works but ignores the fact that rows are already sorted.

Complexity

Time Complexity: O(N × M × log(N × M))
Space Complexity: O(N × M)

Brute Force Code

class Solution {

    public int median(int[][] mat) {

        List<Integer> list = new ArrayList<>();

        for (int[] row : mat) {

            for (int num : row) {
                list.add(num);
            }
        }

        Collections.sort(list);

        return list.get(list.size() / 2);
    }
}

Moving Towards the Optimal Approach

Notice that we don't actually need the sorted array.

We only need:

How many numbers are smaller than or equal to X?

If we can answer this efficiently, we can binary search the median value.

Pattern Recognition

Whenever you see:

Sorted Rows
Find kth smallest / median
Value range known

Think:

Binary Search on Answer

Key Observation

Suppose:

mid = 10

Count:

How many elements ≤ 10 ?

If that count is:

Too small

Median lies on the right.

If count is:

Large enough

Median lies on the left.

Why Upper Bound?

Each row is sorted.

For every row we can find:

Count of elements ≤ mid

using Binary Search.

This takes:

O(log M)

per row.

Optimal Java Solution

class Solution {

    public int median(int[][] mat) {

        int n = mat.length;
        int m = mat[0].length;

        int low = 1;
        int high = 2000;

        int required = (n * m) / 2;

        while (low <= high) {

            int mid = low + (high - low) / 2;

            int count = 0;

            for (int[] row : mat) {
                count += upperBound(row, mid);
            }

            if (count <= required) {
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }

        return low;
    }

    private int upperBound(int[] row, int target) {

        int low = 0;
        int high = row.length - 1;

        while (low <= high) {

            int mid = low + (high - low) / 2;

            if (row[mid] <= target) {
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }

        return low;
    }
}

Dry Run

Input

1  3  5
2  6  9
3  6  9

Total Elements:

Median Position:

9 / 2 = 4

Need the 5th smallest element.

Iteration 1

mid = 5

Count elements ≤ 5:

Row1 → 3
Row2 → 1
Row3 → 1

Total = 5

Since:

5 > 4

Move Left.

Iteration 2

mid = 3

Count elements ≤ 3:

Row1 → 2
Row2 → 1
Row3 → 1

Total = 4

Since:

4 <= 4

Move Right.

Result

Median = 5

Why Binary Search Works?

We are not searching indices.

We are searching values.

For every value:

Count(elements ≤ value)

This count grows monotonically.

Hence Binary Search becomes possible.

Complexity Analysis

Metric	Complexity
Time Complexity	O(log(MaxValue) × N × log M)
Space Complexity	O(1)

Where:

log(MaxValue) → Binary Search on answer.
log(M) → Upper Bound in each row.

Interview One-Liner

Binary search the value range and count how many elements are ≤ mid using upper bound on every sorted row.

Pattern Learned

Sorted Structure
+
Need kth Smallest / Median
+
Monotonic Count

=> Binary Search on Answer

Memory Trick