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

Enter fullscreen mode Exit fullscreen mode

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?

Enter fullscreen mode Exit fullscreen mode

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

Enter fullscreen mode Exit fullscreen mode

Count:

How many elements ≤ 10 ?

Enter fullscreen mode Exit fullscreen mode

If that count is:

Too small

Enter fullscreen mode Exit fullscreen mode

Median lies on the right.

If count is:

Large enough

Enter fullscreen mode Exit fullscreen mode

Median lies on the left.

Why Upper Bound?

Each row is sorted.

For every row we can find:

Count of elements ≤ mid

Enter fullscreen mode Exit fullscreen mode

using Binary Search.

This takes:

O(log M)

Enter fullscreen mode Exit fullscreen mode

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

Enter fullscreen mode Exit fullscreen mode

Dry Run

Input

1  3  5
2  6  9
3  6  9

Enter fullscreen mode Exit fullscreen mode

Total Elements:

9

Enter fullscreen mode Exit fullscreen mode

Median Position:

9 / 2 = 4

Enter fullscreen mode Exit fullscreen mode

Need the 5th smallest element.

Iteration 1

mid = 5

Enter fullscreen mode Exit fullscreen mode

Count elements ≤ 5:

Row1 → 3
Row2 → 1
Row3 → 1

Total = 5

Enter fullscreen mode Exit fullscreen mode

Since:

5 > 4

Enter fullscreen mode Exit fullscreen mode

Move Left.

Iteration 2

mid = 3

Enter fullscreen mode Exit fullscreen mode

Count elements ≤ 3:

Row1 → 2
Row2 → 1
Row3 → 1

Total = 4

Enter fullscreen mode Exit fullscreen mode

Since:

4 <= 4

Enter fullscreen mode Exit fullscreen mode

Move Right.

Result

Median = 5

Enter fullscreen mode Exit fullscreen mode

Why Binary Search Works?

We are not searching indices.

We are searching values.

For every value:

Count(elements ≤ value)

Enter fullscreen mode Exit fullscreen mode

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

Enter fullscreen mode Exit fullscreen mode

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 ?

Enter fullscreen mode Exit fullscreen mode

Count Too Small
→ Move Right

Count Large Enough
→ Move Left

Enter fullscreen mode Exit fullscreen mode

Mental Model

Binary Search on Index
→ Search Position

Binary Search on Answer
→ Search Value

Enter fullscreen mode Exit fullscreen mode

Whenever you hear:

“Median in Sorted Matrix”

your brain should immediately think:

Count Elements ≤ Mid + Binary Search on Answer