Show problems as
Classic problem #1631MediumArrayBinary SearchDepth-First SearchBreadth-First SearchUnion-FindHeap (Priority Queue)MatrixDijkstra's Algorithm

Path With Minimum Effort

Real-world version: Route With the Gentlest Climb
Tracked in this browser only
Read Path With Minimum Effort on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

A survey of a hillside is stored in heights, a rectangle of cells where heights[r][c] is the ground elevation of cell r, c.

A porter begins in the corner cell at row 0, column 0. The drop-off is the opposite corner, the cell in the last row and the last column. One step of a route moves to a cell sharing a full edge with the cell being left, so up, down, left and right are all available, and a route may cross ground it has already covered.

The strain of a route is the largest single climb or drop it contains, that is the largest absolute elevation difference between two cells that the route steps between. A route that never leaves its starting cell has strain 0.

Return the smallest strain reachable by a route joining those two corner cells.

Examples

Example 1

Input
heights = [[1, 10, 6]]
Output
9

The porter has one cell of choice and must cross from 1 to 10 and then from 10 to 6, so the route contains a climb of 9 and a drop of 4, and its strain is 9.

Example 2

Input
heights = [[4, 99, 6, 7, 9], [5, 99, 7, 91, 10], [6, 8, 8, 90, 11]]
Output
2

The route 4, 5, 6, 8, 8, 7, 6, 7, 9, 10, 11 walks down the first column, right along the bottom row to the middle column, up that column to the top row, then right and down the last column. Its steps differ by 1, 1, 2, 0, 1, 1, 1, 2, 1 and 1, so its strain is 2.

Example 3

Input
heights = [[3, 3, 3], [3, 3, 3]]
Output
0

Every cell records the same elevation, so any route has no climb at all.

Constraints

  • rows == heights.length
  • columns == heights[i].length
  • 1 <= rows, columns <= 100
  • 1 <= heights[i][j] <= 10^6

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def minimum_effort_path(heights: list[list[int]]) -> int:
Java
public int minimumEffortPath(int[][] heights)

More on the same topics