Cross the height map with the gentlest worst climb: Dijkstra where a path's cost is its biggest single step, not the total.
▼The problem
LeetCode 1631 (Medium). heights is an m × n grid. Start at the top-left cell and reach the bottom-right one, moving up, down, left or right. A route's effort is the largest absolute height difference between two consecutive cells on it. Return the minimum effort. (Cousins in the series: ../network-delay-time (Dijkstra, relay towers), ../swim-in-rising-water (tide pool), ../pacific-atlantic-water-flow (terraced heightmap); this one has its own look.)
Examples (LeetCode's): [[1,2,2],[3,8,2],[5,3,5]] → 2 (down the left, then along the bottom: 1 3 5 3 5, every step 2; along the top then down, 1 2 2 2 5, has steps 1 0 0 3 so effort 3; walked through in scene 7), [[1,2,3],[3,8,4],[5,3,5]] → 1, and the 5 × 5 one → 0 (the last two are checked in code, not shown).
The solution
def minimumEffortPath(heights):
m, n = len(heights), len(heights[0])
best = [[inf] * n for _ in range(m)]
best[0][0] = 0
heap = [(0, 0, 0)] # (effort, row, col)
while heap:
e, r, c = heappop(heap)
if (r, c) == (m - 1, n - 1):
return e
for nr, nc in (r+1, c), (r-1, c), (r, c+1), (r, c-1):
if 0 <= nr < m and 0 <= nc < n:
step = abs(heights[nr][nc] - heights[r][c])
ne = max(e, step)
if ne < best[nr][nc]:
best[nr][nc] = ne
heappush(heap, (ne, nr, nc))Transcript
Path With Minimum Effort. A grid holds rooftop heights. Get from the top-left roof to the bottom-right, stepping up, down, left or right. A route's effort is its biggest single step. Find the least effort.
Take one, two, two; three, eight, two; five, three, five. Along the top, then down: steps one, zero, zero, three. Effort three. Down the left, then along the bottom: every step is two. Effort two, the answer.
It's not a sum: the first route changes four in total, the second eight, yet the second wins. Like a ladder, it must reach your tallest climb.
The naive way tries every route. Three by three has twelve; six by six, over a million.
Use Dijkstra. Each roof keeps the shortest ladder that reaches it, zero at the start. A min-heap hands back the shortest first. A step to a neighbour needs the larger of that ladder and the height difference. If it's shorter than the neighbour's best, record it and push.
In code, the heap starts at the corner. Pop the smallest. If it's the bottom-right, return it. Otherwise, relax all four neighbours.
Let's walk it. From one, the two costs one, the three costs two. Pop the ones along the top and down the right: the corner is reached, but at three. Three can wait. Pop the twos: three, five, three. The corner drops to two, pops, done.
Order m n log m n time, and order m n space.
Worst step, not the sum. Shortest ladder first. Stop at the corner. That's Path With Minimum Effort.