Path with minimum effort

mediumDijkstra's shortest pathsHeaps target 25 min

Path with minimum effort

Not solved yetLeetCode 1631. Path With Minimum Effort

A delivery robot crosses a field laid out as a grid. heights[r][c] is the height of the ground in the cell at row r, column c. The robot starts in the top-left cell and must reach the bottom-right cell. Each move goes to the next cell up, down, left or right, never off the grid, and a route may visit cells in any order.

The step of a move is the height difference between the two cells, without its sign: going from 3 to 8 and going from 8 to 3 are both steps of 5. The robot's motor only cares about its hardest move, so the effort of a route is its largest step, not the sum of its steps. A route with no moves has effort 0. Return the smallest effort of any route from the top-left cell to the bottom-right cell.

Example 1

Inputheights = [[1, 6, 2], [3, 8, 4], [5, 7, 6]]Output2

Down the left side and along the bottom: 1, 3, 5, 7, 6. Its steps are 2, 2, 2 and 1, so the effort is 2. No route does better, because both first steps (1 to 3, and 1 to 6) are at least 2.

Example 2

Inputheights = [[1, 4, 2]]Output3

One row, so one route: steps of 3 and 2. The effort is the larger one, 3.

Example 3

Inputheights = [[7]]Output0

The start is the goal, so there are no steps and the effort is 0.

Constraints

1 ≤ rows, cols ≤ 100
1 ≤ heights[r][c] ≤ 10⁶

Plan it first

Write a line for each before you code, then say them out loud. Compare with the Approach tab afterwards.

Walk In what order will you visit the input?Notebook What will you write down as you go?Promise What stays true after every step?Cost Time and space, in Big O.

Run examples checks the examples. Submit runs every test, including edge cases and, when the problem has one, a speed check on a large input.

Same pattern