Median of a Row-Wise Sorted Matrix

You are given an m x n matrix in which every row is individually sorted in non-decreasing order (there is no relationship between different rows, and the matrix as a whole is not necessarily sorted). It is guaranteed that m*n is odd. Find the median of all m*n elements of the matrix, without extracting and sorting them directly. Your algorithm should run in O(m * log n * log(maxValue - minValue)) time or better.

Input: The first line contains two integers m and n. Each of the next m lines contains n space-separated integers, one row of the matrix (each row individually sorted ascending). Output: Print a single integer: the median value of all matrix elements.

1 <= m, n <= 1000 1 <= m*n <= 2*10^5, and m*n is odd 1 <= matrix[i][j] <= 10^9 Each row is individually sorted in non-decreasing order.

This is a great example of 'binary search on the answer' applied to a VALUE (not an index) - recognizing that the target of a binary search doesn't have to be an array position, but can be any value in a monotonic value-space, broadens what problems you'll recognize as binary-searchable.

Find the median value of a matrix where every ROW is sorted individually, but rows have no relationship to each other. Brute force: Extract all m*n elements into a flat array, sort it, and directly index into the middle position - this works but costs O(m*n log(m*n)) for the sort, ignoring the ALREADY-sorted structure within each row. Optimised: Binary searching over the VALUE RANGE (rather than array positions) and using each row's OWN sortedness to quickly count 'how many elements in this row are <= v' via a per-row binary search, avoids ever building or sorting a combined flat array - the per-row counts sum up to answer 'how many total elements are <= v' efficiently at each candidate value.

1. Binary search directly over the RANGE OF POSSIBLE VALUES (from the smallest to largest matrix value), not over array indices - the candidate is a VALUE you're searching for, not a position. 2. For a candidate value v, count how many matrix elements are <= v by running a binary search (upper bound) WITHIN EACH ROW and summing the per-row counts - this is exactly where each row's individual sortedness pays off. 3. The median is the SMALLEST value v whose count of elements <= v reaches (total elements + 1) / 2.

Time: O(m * log n * log(maxValue - minValue)) - for each of the O(log(value range)) binary search steps on the value, counting takes O(m log n) (one binary search per row). Space: O(1) extra space beyond the input matrix.

m = 1 (the median is just the middle element of the single sorted row); the same value may repeat many times across different rows.

Be ready to explain the two NESTED binary searches clearly: an OUTER binary search over candidate VALUES, and an INNER binary search (per row) to COUNT how many elements qualify - conflating these two different binary searches is a common source of confusion.