Path With Minimum Effort
Medium · shortest path
A hiker is standing on the top-left cell of a rectangular map and wants to reach the bottom-right cell. The map is given as a grid heights, where heights[r][c] is the height of the cell in row r and column c.
From a cell the hiker can move one step up, down, left or right, to a cell that is on the map. The hiker may visit the same cell more than once.
The effort of a route is the largest height difference between two cells that are next to each other on the route. Only single steps count: the effort is not the sum of the differences, and not the difference between the start and the end.
Return the smallest effort over all routes from the top-left cell to the bottom-right cell. If the map is a single cell, the hiker is already there and the answer is 0.
Examples
Example 1
Input: heights = [[1, 10], [2, 3]]
Output: 1
Going right first means a step of 9. Going down first means steps of 1 and 1, so the effort is 1.
Example 2
Input: heights = [[5, 9, 2, 7]]
Output: 7
There is only one route along the row, with steps of 4, 7 and 5. The largest is 7.
Example 3
Input: heights = [[1, 8, 1], [1, 9, 1], [1, 1, 1]]
Output: 0
Walking down the left column and along the bottom row never changes height, so the effort is 0 even though the route is longer.
Constraints
- 1 <= rows, cols <= 100, where rows is the number of rows and cols is the number of columns of heights
- 0 <= heights[r][c] <= 10^6