#1631
Path With Minimum Effort
specialist · 665 · lc medium +30 · verified · 62.8% accepted · 6,789 likes · top 64%
Description
You are given a 2D heights grid where each cell holds an elevation. Starting at (0, 0) and moving to (rows-1, columns-1) via adjacent cells, a path's effort is the maximum absolute elevation difference between any two consecutive cells. Return the minimum possible effort over all paths.
Example 1:
Input: heights = [[1,2,2],[3,8,2],[5,3,5]]
Output: 2
Explanation: The route of [1,3,5,3,5] has a maximum absolute difference of 2 in consecutive cells.
This is better than the route of [1,2,2,2,5], where the maximum absolute difference is 3.
Example 2:
Input: heights = [[1,2,3],[3,8,4],[5,3,5]]
Output: 1
Explanation: The route of [1,2,3,4,5] has a maximum absolute difference of 1 in consecutive cells, which is better than route [1,3,5,3,5].
Example 3:
Input: heights = [[1,2,1,1,1],[1,2,1,2,1],[1,2,1,2,1],[1,2,1,2,1],[1,1,1,2,1]]
Output: 0
Explanation: This route does not require any effort.
Code
1
2
3