Matrix Median

Matrix median gives a matrix whose rows are each sorted and asks for the median of all elements, with an odd total count. Flattening and sorting is O(nm log(nm)) and ignores the structure entirely. The reframing is to search for the value rather than a position. The median is the smallest value with strictly more than half the elements less than or equal to it. So if you could count elements ≤ some candidate x quickly, you could test any candidate. Counting is easy precisely because the rows are sorted — each row answers "how many of mine are ≤ x?" with a binary search in O(log m). Across n rows that is O(n log m), far cheaper than touching every element. And the count is monotone in x: raising the candidate can only increase it. That is exactly the structure binary search needs, so: - Binary search the value range, from the smallest first-column entry to the largest last-column entry. When the count is at most half, the median must be larger; otherwise it is this value or smaller. The loop converges on the first value whose count exceeds half. A subtle point: that converged value is guaranteed to be present in the matrix, because the count only changes at values that actually occur. So the search naturally lands on a real element rather than a gap between two.

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.