952. Grid Row Median
A weather agency stores yearly rainfall readings of R stations, one station per row of grid, with C readings per station. Both R and C are odd, so the total number of readings is odd, and each row is already sorted in non-decreasing order. Different rows are unrelated to each other.
Return the median of all R * C readings: the value that would sit exactly in the middle if every reading were written in one sorted list. Equal readings count separately, so the median is simply the ((R * C + 1) / 2)-th smallest value. The result is always one of the readings. Try not to merge or sort all readings together.
Example 1
- Input:
- grid = [[2,4,9],[1,5,6],[3,3,8]]
- Output:
- 4
- Explanation:
The nine values sorted are 1,2,3,3,4,5,6,8,9; the fifth smallest, 4, is the median.
Example 2
- Input:
- grid = [[7,7,7],[7,7,7],[1,8,9]]
- Output:
- 7
- Explanation:
Sorted: 1,7,7,7,7,7,7,8,9; the middle (fifth) value is 7.
Example 3
- Input:
- grid = [[10,20,30,40,50]]
- Output:
- 30
- Explanation:
One row of five values: the median is its third value, 30.
Constraints
- 1 ≤ R, C ≤ 999, and both R and C are odd
- -109 ≤ grid[i][j] ≤ 109
- Each row is sorted in non-decreasing order
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 600 msC++ 150 msJava 300 msJavaScript 300 msTypeScript 300 ms
Expected complexity
- Time
- O(R * log C * log(maxValue - minValue))
- Space
- O(1)