Advanced Graphs Weighted shortest paths
472. Path With Minimum Effort
You are given a grid of heights, heights. heights[i][j] is the height of the cell in row i, column
j. You start in the top-left cell and want to reach the bottom-right cell. Each step moves to the cell
directly above, below, left or right. A path may turn and go back the way it came as often as it likes.
The effort of a path is the largest difference in height between two cells that come one after the other on it. Return the smallest effort of any path from the top-left cell to the bottom-right cell.
Example 1
Input: heights = [[2, 8, 6, 6], [4, 6, 3, 7], [7, 1, 8, 6]]
2Explanation: The path 2 → 4 → 6 → 8 → 6 → 6 → 7 → 6 goes down, right, back up, along the top row and down the right side. No step on it changes the height by more than 2.
Example 2
Input: heights = [[5, 1, 8, 3]]
7Explanation: There is only one path, and its largest step is from 1 to 8.
Example 3
Input: heights = [[1000000000, 1], [1, 1000000000]]
999999999Explanation: Every path passes a cell of height 1, and the step down to it is 999999999.
Check your understanding
Work out the answer for this input before you write any code.
Constraints
m == heights.length,n == heights[i].length1 ≤ m, n ≤ 1051 ≤ m · n ≤ 1051 ≤ heights[i][j] ≤ 109
Clarifying questions
What you would ask an interviewer before writing any code.