You are given a matrix mat of size n x m in which every row is sorted in non-decreasing order. Both n and m are guaranteed to be odd.
Return the median of the matrix — the element that would sit exactly in the middle if all n * m values were lined up in sorted order.
Because n * m is odd, the median is always a single, well-defined element of the matrix; you never average two middle values. Note that only the rows are sorted — there is no ordering guarantee between different rows.
n*m elements works, but the rows are already sorted individually — and the median is just the element of a specific rank. Can you aim for that rank directly?(n*m)/2 + 1 elements are <= x, counting per row with an upper-bound binary search.n * m odd, so the sorted order has a single middle element. You never have to average two middle values — the median is always an actual element of mat.x whose count of elements <= x reaches the median rank. If x were absent from the matrix, x - 1 would have the identical count, contradicting that x was the smallest such value.mat[1][0] can be smaller than mat[0][2]. That is why the value-range bounds scan every row's first and last elements instead of trusting row 0.k and rank k + 1 and combine the two results.<= x in O(n + m) per probe instead of O(n log m), shaving a log factor off the counting step.need = k. An alternative is a min-heap over the row heads, popping k times for O(k log n) — better when k is tiny, worse when k is near n*m/2.Input: n = 3, m = 3, mat = [[1, 3, 5], [2, 6, 9], [3, 6, 9]] Output: 5 All elements in sorted order: [1, 2, 3, 3, 5, 6, 6, 9, 9]. The middle (5th of 9) element is 5.
Input: n = 3, m = 3, mat = [[2, 4, 9], [3, 6, 7], [4, 7, 10]] Output: 6 All elements in sorted order: [2, 3, 4, 4, 6, 7, 7, 9, 10]. The middle element is 6.
Input: n = 3, m = 1, mat = [[3], [4], [8]] Output: 4 All elements in sorted order: [3, 4, 8]. The middle element is 4.
- 1 <= n, m <= 400 - n and m are both odd - 1 <= mat[i][j] <= 2000
Half the matrix stands below one element and half stands above it — and you can find that element without ever sorting the matrix. This tutorial walks from the honest flatten-and-sort baseline to one of the most elegant patterns in interviews: binary search on the answer.
x — found in O(log m).k elements, the median is the element of rank k/2 + 1 (1-indexed) in sorted order.In plain terms: if you listed all n * m elements in sorted order, return the one in the exact middle. Formally, return the element of rank (n*m)/2 + 1 (1-indexed). Since n and m are both odd, n * m is odd and that middle element always exists uniquely.
Worked example — mat = [[1, 3, 5], [2, 6, 9], [3, 6, 9]]
mat = [ 1 3 5 ]
[ 2 6 9 ]
[ 3 6 9 ]
all 9 elements, sorted: 1 2 3 3 [5] 6 6 9 9
^ rank 5 of 9 → median = 5
Asking two or three sharp questions before coding shows you hunt for the guarantees your algorithm will lean on.
“Is every row guaranteed to be sorted in non-decreasing order?”
Yes — and the fast solution leans on it. Without sorted rows, counting elements at most x costs O(m) per row instead of O(log m).
“Are n and m always odd?”
Yes — so n * m is odd and the median is a single element, never the average of two middles.
“Can the matrix be a single row or a single column?”
Yes — n = 1 or m = 1 are valid, and the answer is simply the middle of that one sorted line.
“Can the same value appear in several rows?”
Absolutely. Duplicates across rows are common, and the counting approach must handle them — this is exactly where naive equality checks break.
“How large can the matrix get?”
Up to 400 x 400 = 160,000 elements. Flatten-and-sort actually runs in time — but it spends O(n*m) memory and ignores the sorted rows entirely.
“What is the range of the values?”
Between 1 and 2000 — a tiny value space, so a binary search over values converges in about 11 probes.
Before I code, let me confirm the guarantees.
Every row is individually sorted, but there is no ordering between rows — correct?
Both dimensions are odd, so the median is always one element and I never average two middles.
Since only rows are sorted, I am thinking of counting elements below a guessed value rather than merging everything.
You never need the full sorted order — only the element whose rank is need = (n*m)/2 + 1. For 9 elements that is rank 5: the value with at least 5 elements at or below it, found as early as possible. Finding a k-th smallest is a counting problem, not a sorting problem.
For any candidate x, one upper-bound binary search per row reports how many of its elements are <= x.
row = [2, 6, 9], x = 5
≤5 >5 >5 → upper bound lands at index 1 → 1 element ≤ 5Summing over all rows gives the matrix-wide count in O(n log m) — without touching most elements.
As x grows, the count of elements <= x never decreases. So the predicate count(x) >= need is false, false, …, then true forever — it flips exactly once. Binary search the value range for the smallest x where it turns true. That x must be an element of the matrix: if it were absent, x - 1 would have the identical count, contradicting that x was the smallest.
| Brute force | Optimal | |
|---|---|---|
| Time | O(nm log(nm)) | O(n · log m · log(maxV)) |
| Space | O(nm) | O(1) |
| Idea | flatten + sort, read the middle | binary search the value, count per row |
Both are worth knowing — full code for each lives in the Approaches selector below.
Key takeaway
When data is sorted in pieces but not globally, don't merge — binary search the answer. Turn find the k-th smallest into the monotonic question how many elements are at most x?, which every sorted piece answers in logarithmic time.
need = (n*m)/2 + 1
lo = min of every row's first element, hi = max of every row's last element
while lo < hi:
mid = (lo + hi) / 2
if (sum over rows of upper_bound(row, mid)) < need: lo = mid + 1
else: hi = mid
return lo