Matrix Median
Rows of the matrix are sorted. Find the overall median without flattening (odd element count).
Open on GeeksforGeeks ↗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.
Same binary-search-the-answer idea, but the predicate counts rather than places. You search over values, and for each guess ask how many entries are ≤ it — cheap, because every row is sorted and answers in O(log m). Recognise the trick: when the whole structure is too big to merge, count against a guess instead.
Approach
Binary search on value, not position
Search lo=min(first column) to hi=max(last column). No element order across rows needed.
Count ≤ mid per row
Each sorted row answers 'how many ≤ mid' via bisect in O(log m); total count in O(n log m).
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).
Solution & live demo
Common pitfalls
Merging all rows and sorting
flat = sorted(x for row in mat for x in row) return flat[(n * m) // 2]
count = sum(bisect_right(row, mid) for row in mat)
Correct, but O(nm log nm) time and O(nm) space when the rows are already sorted. Binary searching values costs O(n log m log(range)) and allocates nothing.
Using bisect_left for the count
count = sum(bisect_left(row, mid) for row in mat)
count = sum(bisect_right(row, mid) for row in mat)
You need the number of elements less than or equal to mid. bisect_left excludes elements equal to it, so every duplicate of the candidate goes uncounted and the search settles one value too low.
Terminating with lo <= hi and returning mid
while lo <= hi:
...
return midwhile lo < hi:
...
return loThe median must be an element that actually appears, and a mid satisfying the count condition need not be one. Converging with lo < hi and returning lo lands on a real matrix entry.
Edge cases
Median is the middle of that row — the search still lands there.
Counting ≤ handles ties naturally; convergence lands on the duplicated value.