Median in a row-wise sorted matrix

Hard

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

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
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;
}