Median of a Row Wise Sorted Matrix - Video Solutions

Problem Overview: You are given a matrix where every row is individually sorted. The task is to compute the median of all elements without flattening the matrix into a single array. Since rows are sorted but columns are not guaranteed to be sorted, traditional median techniques need modification.

Approach 1: Flatten and Sort (O((r*c) log(r*c)) time, O(r*c) space)

The most straightforward method is to copy every element from the matrix into a single array and sort it. After sorting, the median is simply the element at index (r*c)/2. This works because sorting produces the global order of all values. The downside is the extra memory and sorting cost, which becomes expensive for large matrices.

This approach is mainly useful as a baseline or when constraints are small. It ignores the fact that each row is already sorted, so it fails to leverage the structure of the problem.

Approach 2: Min Heap Merge (O(r*c log r) time, O(r) space)

Treat each row as a sorted list and perform a k-way merge using a min heap. Insert the first element from every row into the heap. Repeatedly extract the smallest element and push the next element from the same row. After extracting (r*c)/2 + 1 elements, the last popped value is the median.

This technique is similar to merging k sorted arrays. It reduces memory compared to flattening the matrix and avoids sorting the entire dataset. However, the heap operations still make it slower than the optimal solution when the matrix grows large.

Approach 3: Two Binary Searches (O(r log c log valueRange) time, O(1) space)

The optimal method performs binary search on the value range rather than on indices. The smallest candidate value is the minimum of the first column, and the largest candidate value is the maximum of the last column. For a guessed value mid, count how many elements in the matrix are less than or equal to it.

Each row is sorted, so you can run a binary search (upper bound) in that row to find how many elements are ≤ mid. Summing across rows gives the total count. If the count is less than the desired median position (r*c+1)/2, move the search range higher; otherwise move it lower.

This double binary search efficiently narrows the median without scanning all elements. The outer search runs on the value range, while the inner search uses row ordering. It relies heavily on Binary Search and the structure of a sorted Matrix. The matrix values are accessed directly without extra storage, making the solution space efficient.

Recommended for interviews: Interviewers expect the two binary search solution. Starting with flatten-and-sort shows understanding of the problem, but the optimized method demonstrates deeper knowledge of Array search patterns and how to exploit sorted structure. It scales well even when the matrix contains millions of elements.