Matrix Median
HardBinary search the value, count ≤ mid
Guess a value and count how many grid numbers are below it; adjust until exactly half are below.
The idea
Binary search on the answer value: count how many entries are ≤ mid across all rows (each row via upper bound). The median is the smallest value with more than half the entries ≤ it.
lo
hi
1
2
3
4
5
6
7
8
9
0
1
2
3
4
5
6
7
8
Step 1 of 6. 3×3 matrix, median = 5th smallest of 9. Binary search the value. Values: 1, 2, 3, 4, 5, 6, 7, 8, 9. Pointers: lo at index 0, hi at index 8.
1/6
Optimal
timeO(32·rows·log cols)spaceO(1)
Count with per-row upper bound.
1let lo = min, hi = max, need = (rows * cols) / 2;2while (lo < hi) {3 const mid = (lo + hi) >> 1;4 let cnt = 0;5 for (const row of grid) cnt += upperBound(row, mid);6 if (cnt > need) hi = mid;7 else lo = mid + 1;8}9return lo;Input
- array
- [1, 2, 3, 4, 5, 6, 7, 8, 9]
Memory
- lo
- = 0 [1]
- hi
- = 8 [9]
- mid
- —
- count ≤ x
- —
Output
- count ≤ x
- —
- answer
- —
Check yourself
3 quick questions about this walkthrough. A wrong answer costs nothing.
Examples
Example 1
- Input:
- matrix = [[1,3,5],[2,6,9],[3,6,9]]
- Output:
- 5
- Explanation:
- The middle of all 9 values is 5.
Example 2
- Input:
- matrix = [[1,1,1],[2,2,2],[3,3,3]]
- Output:
- 2
- Explanation:
- Median of the 9 values is 2.
Example 3
- Input:
- matrix = [[1]]
- Output:
- 1
- Explanation:
- One cell is its own median.
Practice this problem:GeeksforGeeks(opens in a new tab)
Finished the walkthrough? Add it to your streak.