Ward Quiet Access Map
Minimum peak value on right/down grid paths from top-left to each cell
A hospital ward has a rectangular arrangement of bays. The integer ratings[r][c] is the disturbance rating of entering bay (r, c).
A supply cart starts in the top-left bay (0, 0). On each move, it may enter the bay immediately to the right or immediately below its current bay. The disturbance of a route is the largest rating among all bays on that route, including the starting and destination bays.
Return a matrix with the same dimensions as ratings. Its entry at (r, c) must be the smallest possible disturbance of any allowed route from (0, 0) to (r, c).
Each destination is considered independently; the cart does not need to visit all destinations in one route.
Examples
Example 1
Input: ratings = [[2,9],[3,4]] Output: [[2,9],[3,4]]
For destinations in the first row or first column, there is only one allowed route. For the bottom-right bay, compare the route through the high-rated top-right bay with the route through the lower-rated bottom-left bay.
Example 2
Input: ratings = [[1,2,3],[2,10,4],[3,4,2]] Output: [[1,2,3],[2,10,4],[3,4,4]]
The high-rated center bay need not be entered to reach the bottom-right bay: the cart can travel across the top row and then down the rightmost column. Reaching the center itself still requires including its rating.
Example 3
Input: ratings = [[7]] Output: [[7]]
There is only one bay, so its route consists solely of the starting bay.
Constraints
- 1 <= ratings.length <= 100
- 1 <= ratings[0].length <= 100
- All rows of ratings have the same length.
- 0 <= ratings[r][c] <= 1000000
The intended solution runs in O(rows * columns) time. The returned matrix occupies O(rows * columns) space; no additional matrix is needed. Ratings are nonnegative, and every bay is reachable under the allowed moves.
Hints
Show hint 1Hint 1
For each bay, store the smallest possible maximum rating encountered on a route ending there.
Show hint 2Hint 2
An interior bay can only be entered from above or from the left. Choose the better predecessor, then include the current bay's rating.
Follow-up questions
What an interviewer might ask once you have a working solution.
- How would you compute only the bottom-right answer using memory proportional to the number of columns?
- How would you also reconstruct an optimal route to a requested destination, preferring a right move whenever both choices permit an optimal completion?
Practice this with an AI interviewer
Explain your approach out loud, write Python or JavaScript, run it against hidden tests (including large inputs), and get a scored debrief.
Start this problem