Path with minimum effort

Hard

Dijkstra where cost = the biggest single step

Problem

Find a path from top-left to bottom-right minimizing the maximum absolute height difference between adjacent cells.

In simple words

Dijkstra where a path's cost is its single biggest height jump; minimise that worst step.

The idea

This is Dijkstra with a twist: a path's cost is not the sum of steps but the single largest height jump along it. So relaxing a neighbour sets its cost to max(cost-so-far, |height difference|). The priority queue always expands the cell reachable with the smallest maximum-jump; the first time the bottom-right cell is settled you have the minimum effort.

←→stepspaceplay

dist[0, ∞, ∞, ∞, ∞]

settled—

1/13

Optimal

timeO(mn log mn)spaceO(mn)

1effort[start] = 0, all others = ∞2min-heap H = {(0, start)}3while H not empty:4  (e, cell) = pop-smallest effort5  for each neighbour nb of cell:6    step = max(e, |height[cell] - height[nb]|)7    if step < effort[nb]: effort[nb] = step; push (step, nb)8return effort[bottom-right]

Input

nodes: 5, 6 edges

Memory

dist: [0, ∞, ∞, ∞, ∞]
frontier: —

Output

settled: —
shortest dist: —

Check yourself

3 quick questions about this walkthrough. A wrong answer costs nothing.

Examples

Example 1

Input:: heights = [[1,2,2],[3,8,2],[5,3,5]]
Output:: 2
Explanation:: The route down the right keeps the biggest step at 2.

Example 2

Input:: heights = [[1,2,3],[3,8,4],[5,3,5]]
Output:: 1
Explanation:: Best effort is 1.

Example 3

Input:: heights = [[1,10],[1,1]]
Output:: 0
Explanation:: Go around the 10 → effort 0.

Practice this problem:LeetCode(opens in a new tab)Search GeeksforGeeks(opens in a new tab)

Finished the walkthrough? Add it to your streak.