38. Find Median in a Row-Wise Sorted Matrix

Given an r x c matrix where every row is individually sorted ascending, find the median of all r*c elements combined. Print the median rounded to exactly one decimal place.

Input: The first line contains r and c, space-separated. The next r lines each contain c space-separated integers, sorted ascending within each row. Output: Print the median of all r*c elements, rounded to exactly one decimal place.

1 <= r, c <= 400

This is essentially the 2D generalization of the classic 'median of two sorted arrays' problem - recognizing that connection helps frame both problems as variations on the same underlying 'find the middle of several sorted sequences combined' theme.

Given a grid where every row is individually sorted, find the median value across all its cells combined. Brute force: Flattening and sorting is already a simple, fully correct approach for the constraints given here (r, c up to 400, so at most 160,000 elements) - not really a 'worse' method, just a more general one than exploiting the row-sortedness. Optimised: For LARGER matrices, a binary search over the possible VALUE range works well: for a candidate median value, count how many matrix elements are less than or equal to it (using binary search WITHIN each already-sorted row) to check if it's positioned correctly - this avoids a full flatten-and-sort, but a plain sort remains fully acceptable and simpler for these constraints.

Flatten all r*c elements from every row into a single array, sort that combined array, and read off the middle element (or average of the two middle elements for an even count) as the median. This is a direct, obviously correct application of the definition of median, but it throws away the fact that each individual row is already sorted, so it pays for a full sort of everything from scratch. Time: O(r*c log(r*c)) Space: O(r*c)

Since each row is already individually sorted, push the first element of every row (along with its row and column index) into a min-heap of size r, then repeatedly pop the smallest element and push the next element from the same row, exactly like merging k sorted lists. Stop once enough elements have been popped to reach the median position(s) rather than draining the whole heap. This exploits the existing per-row order to avoid a full re-sort, replacing the log(r*c) factor of a general sort with a much smaller log(r) factor per element, and only needs heap-sized extra memory instead of a full copy of every element. Time: O(r*c log r) Space: O(r)

Binary search over the range of possible values (from the smallest to the largest element in the matrix): for a candidate value x, count how many matrix elements are less than or equal to x by binary searching within each of the r sorted rows (O(log c) per row), and narrow the search range based on whether that count is below or at least the target median rank. The smallest value whose count-of-elements-less-or-equal reaches the median rank is the median. This never materializes or merges the elements at all, working purely on counts, which reduces the auxiliary space to constant and the time to a small number of row binary searches per step of an outer binary search over the value range. Time: O(r log c log(maxVal - minVal)) Space: O(1)

1. The straightforward approach: flatten every row's values into one big list. 2. Sort that combined list. 3. The median is the middle value (or the average of the two middle values) of the sorted combined list.

Time: O(r*c log(r*c)) for the flatten-and-sort approach - dominated by the sort of all combined elements. Space: O(r*c), for the flattened combined list.

r = 1 (a single sorted row); r*c even (median averages two middle values) versus odd (a single middle value); and r = c = 400 (largest, confirming a binary-search-over-values approach is efficient).

Be ready to mention the binary-search-over-value-range technique as the more advanced, specialized approach for very large matrices, even while defaulting to the simpler flatten-and-sort for typical constraints - showing awareness of both options is valuable.