DSA Tracker

Visualize

Path With Minimum Effort

Grid as a graph: Dijkstra with a minimax relax instead of a sum

time O(m * n * log(m * n))space O(m * n)

The trap in this problem is reaching for a sum, because effort is defined as the worst single step, not the total climb. That single change is what lets Dijkstra apply: relaxing an edge takes the MAX of the path's cost so far and the new edge's weight instead of adding them, and that relaxation still only ever raises or holds a cell's effort — never lowers it once the queue has settled it, which is exactly the property Dijkstra needs to guarantee that popping the smallest remaining effort is final. The picture below turns the grid into a graph: one vertex per cell, one weighted edge per adjacent pair, and a badge on each visited cell showing its settled effort.

Details

Animated on: A 3x3 grid of elevations [[1,2,2],[3,8,2],[5,3,5]] — find a path from the top-left to the bottom-right that minimizes the LARGEST absolute height difference between any two consecutive cells on the path, not the total climbed.

Problem:Path With Minimum EffortMedium

Pattern:Shortest Path

Grid as a graph: Dijkstra with a minimax relax instead of a sum

step 1 / 11

Grid as a graph: one vertex per cell, edge weight = height difference

Every cell becomes a vertex and every edge to a 4-directional neighbor carries the absolute height difference as its weight. A path's cost here is the LARGEST edge it uses, not the sum of edges, so the question is which route keeps that single worst step as small as possible.

Pseudocode
1FUNCTION minEffort(heights):
2  effort[0][0] <- 0, all others <- INFINITY
3  queue <- {(0, 0)}
4  WHILE queue NOT EMPTY
5    (r, c) <- CELL IN queue WITH MIN effort
6    REMOVE (r, c) FROM queue
7    IF (r, c) = (m - 1, n - 1)
8      RETURN effort[r][c]
9    FOR EACH neighbor (nr, nc) OF (r, c)
10      cost <- MAX(effort[r][c], ABS(heights[r][c] - heights[nr][nc]))
11      IF cost < effort[nr][nc]
12        effort[nr][nc] <- cost
13        ADD (nr, nc) TO queue

← / → step · space play · Home restart

Every step in words

Show all 11 steps
  1. Every cell becomes a vertex and every edge to a 4-directional neighbor carries the absolute height difference as its weight. A path's cost here is the LARGEST edge it uses, not the sum of edges, so the question is which route keeps that single worst step as small as possible.
  2. effort[0][0] <- 0 and every other cell starts at infinity — nothing else is reachable yet, and reaching the start costs nothing because no step has been taken.
  3. Cell (0,0) settles at effort 0. Stepping to (1,0) at 2 and (0,1) at 1 beats what they had before, so both join the queue.
  4. Cell (0,1) settles at effort 1. Stepping to (1,1) at 6 and (0,2) at 1 beats what they had before, so both join the queue.
  5. Cell (0,2) settles at effort 1. Stepping to (1,2) at 1 beats what it had before, so it joins the queue.
  6. Cell (1,2) settles at effort 1. Stepping to (2,2) at 3 beats what it had before, so it joins the queue.
  7. Cell (1,0) settles at effort 2. Stepping to (2,0) at 2 and (1,1) at 5 beats what they had before, so both join the queue.
  8. Cell (2,0) settles at effort 2. Stepping to (2,1) at 2 beats what it had before, so it joins the queue.
  9. Cell (2,1) settles at effort 2. Stepping to (2,2) at 2 beats what it had before, so it joins the queue.
  10. Popped the destination (2,2) at effort 2. The queue always yields the SMALLEST remaining effort next, so nothing still waiting could ever produce a cheaper route here — this is final. RETURN 2.
  11. Walking the parent pointers back from (2,2) to (0,0) gives 0,0 -> 1,0 -> 2,0 -> 2,1 -> 2,2. Its worst single step is 2, and no other route can beat that — RETURN 2.

Now solve it yourself

Watching is the first half. The second is writing it without the animation.

Solve Path With Minimum Effort in the editorAll Graph problemsBack to roadmap