Find the Median of All Elements in a Row-Sorted Matrix
Implement matrixMedian
Given a matrix with an odd number of elements, where every row is individually sorted in ascending order, return the median of all the elements combined.
Solve it without sorting the whole matrix: binary-search over the range of possible values rather than positions. For each candidate value, count how many elements are ≤ it (a per-row binary search, since rows are sorted) — the smallest value whose count passes the halfway mark is the median.
Example 1:
Input: matrix = [[1,3,5],[2,4,6],[3,5,7]]
Output: 4
Example 2:
Input: matrix = [[1,2,3]]
Output: 2
Example 3:
Input: matrix = [[5]]
Output: 5
+ 4 hidden test cases run on Submit.
Constraints:
- ●
1 ≤ matrix.length, matrix[0].length ≤ 100 - ●
matrix.length × matrix[0].length is odd (so the median is a single element, never an average) - ●
-10⁵ ≤ matrix[i][j] ≤ 10⁵ - ●
Every row is sorted in ascending order
matrix =
[[1,3,5], [2,4,6], [3,5,7]]