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:

9

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

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

Similar Problems

• Median in Matrix
• Kth Smallest Element in Matrix
• Aggressive Cows
• Koko Eating Bananas
• Nth Root of Number
• Capacity to Ship Packages

Memory Trick

Think:

Guess a Number (mid)

Count:
How many elements ≤ mid ?

Count Too Small
→ Move Right

Count Large Enough
→ Move Left

Mental Model

Binary Search on Index
→ Search Position

Binary Search on Answer
→ Search Value

Whenever you hear:

"Median in Sorted Matrix"

your brain should immediately think:

Count Elements ≤ Mid + Binary Search on Answer