Median Of Row Wise Sorted Matrix
01 · Problem
You are given an r x c integer matrix matrix in which each row is sorted in non-decreasing order. The total number of cells r * c is guaranteed to be odd.
Return the median of all r * c values: the value that would sit at index (r * c) / 2 (0-indexed, integer division) if every element were placed into a single sorted list. Duplicates are kept.
Aim to solve it without building and sorting that combined list.
02 · Examples
matrix = [[1,3,5],[2,6,9],[3,6,9]]
5
All values in sorted order are 1, 2, 3, 3, 5, 6, 6, 9, 9. The middle (5th) value is 5.
matrix = [[1],[2],[3]]
2
Sorted values are 1, 2, 3, so the median is 2.
matrix = [[1,1,3,3,4]]
3
A single sorted row; the 3rd of 5 values is 3.
03 · Constraints
- 011 <= r, c <= 500
- 02r * c is odd
- 031 <= matrix[i][j] <= 109
- 04Each row of matrix is sorted in non-decreasing order
04 · Optimal complexity
- Time
- O(r * log(c) * log(max - min))
- Space
- O(1)
Practice it alone or rehearse it as an interview.
Practice Mode gives you an editor and test runs, nothing else. AI Interview Mode puts a voice interviewer on the other side, adds a clock, and ends with a scored summary of the round.