GeeksforGeeks Medium

Matrix Median

Rows of the matrix are sorted. Find the overall median without flattening (odd element count).

binary-searchmatrix

02

Intuition

💡

The median is the smallest value with more than half the elements ≤ it. 'How many elements ≤ x' is countable fast — binary search each sorted row — and it's monotone in x, so binary search the value range for the first x whose count exceeds n·m/2.

03

Approach

1

Binary search on value, not position

Search lo=min(first column) to hi=max(last column). No element order across rows needed.

2

Count ≤ mid per row

Each sorted row answers 'how many ≤ mid' via bisect in O(log m); total count in O(n log m).

3

First value passing half wins

If count ≤ half, median is bigger → lo = mid+1; else hi = mid. Loop converges on the median itself (it must be present because counts jump only at matrix values).

04

Solution & live demo

python

▶1from bisect import bisect_right
▶2 
▶3def matrix_median(mat):
▶4    n, m = len(mat), len(mat[0])
▶5    lo = min(row[0] for row in mat)
▶6    hi = max(row[-1] for row in mat)
▶7    need = (n * m) // 2
▶8    while lo < hi:
▶9        mid = (lo + hi) // 2
▶10        count = sum(bisect_right(row, mid) for row in mat)
▶11        if count <= need: lo = mid + 1
▶12        else: hi = mid
▶13    return lo

05

Edge cases

Single row

Median is the middle of that row — the search still lands there.

Heavy duplicates

Counting ≤ handles ties naturally; convergence lands on the duplicated value.

06

Complexity

Time

O(n log m · log R)

Space

O(1)

R = value range; counting is n rows × log m.