Median of a Grid With Sorted Rows
HardBinary Search
Problem
A grading system stores scores in an m × n grid. Each row is sorted in non-decreasing order, but nothing is known about the columns. The total number of cells m · n is odd.
Return the median of all the scores, using less than O(m · n) extra memory.
Example 1
- Input:
- grid = [[1, 3, 5], [2, 6, 9], [3, 6, 9]]
- Output:
- 5
All values sorted: 1, 2, 3, 3, 5, 6, 6, 9, 9. The middle (5th) is 5.
Example 2
- Input:
- grid = [[1], [2], [3]]
- Output:
- 2
Example 3
- Input:
- grid = [[4, 8, 9]]
- Output:
- 8
Constraints
- 1 ≤ m, n ≤ 500
- m · n is odd
- -10^9 ≤ grid[i][j] ≤ 10^9
- Each row is sorted in non-decreasing order.
Hint
Show the first hint
The median is the smallest value x such that at least (m·n + 1) / 2 cells are ≤ x.
Walkthrough
How to approach it
01Clarify before coding
- Are columns sorted? No, only rows. The two-way staircase trick does not apply.
- Is the count odd? Yes, so the median is a single cell value.
- How large can values be? ±10^9, so a value-range binary search takes about 31 steps.
02Brute force
Copy every cell into one list, sort it and take the middle. Or merge the m rows with a heap up to the middle.
Cost: Sorting: O(mn log(mn)) time, O(mn) memory. Heap merge: O(mn/2 · log m) time, O(m) memory.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.