Median in a row-wise sorted matrix
Problem
Given an R × C matrix where each row is sorted and R × C is odd, return the median of all its elements without flattening and sorting them.
Example 1
Input: [[1,3,5], [2,6,9], [3,6,9]] Output: 5
Sorted: 1 2 3 3 5 6 6 9 9. The middle value is 5.
Also asked as: Find median in a row wise sorted matrix
Test cases
Case 1
Input: [[1,3,5],[2,6,9],[3,6,9]] Expected: 5
Case 2
Input: [[1,3,8],[2,3,4],[1,2,5]] Expected: 3
Case 3
Input: [[1],[2],[3]] Expected: 2
Case 4
Input: [[5]] Expected: 5
View solutionHide solution1 approach
1. Binary search on the value
Time O(R · log C · log(range))Space O(1)
For a candidate value, count how many cells are ≤ it (binary search per row). The median is the smallest value with count ≥ (R·C+1)/2.
function matrixMedian(m) { const R = m.length, C = m[0].length, need = (R * C + 1) >> 1; let lo = Math.min(...m.map((row) => row[0])); let hi = Math.max(...m.map((row) => row[C - 1])); const countLE = (x) => m.reduce((acc, row) => { let l = 0, r = C; while (l < r) { const mid = (l + r) >> 1; row[mid] <= x ? (l = mid + 1) : (r = mid); } return acc + l; }, 0); while (lo < hi) { const mid = (lo + hi) >> 1; countLE(mid) < need ? (lo = mid + 1) : (hi = mid); } return lo;}