Your free access ends in 7 days — and you haven’t tried it yet. Watch one algorithm run, start to finish. It takes about two minutes.

Try one problem
0
Problem

Path With Minimum Effort

LeetCode #1631Medium
Dijkstra on a grid · minimize the max step

Given a grid of cell heights, travel from the top-left to the bottom-right moving in four directions. A path's effort is the maximum absolute height difference between consecutive cells; return the minimum possible effort over all paths.

Asked atAmazonGoogle
step 1 / 23
3 × 3 effort grid · cell = best max-diff to reach it
∞
∞
∞
∞
∞
∞
∞
∞
∞
src
min-effort priority queue
front →
(empty)
← back
Dijkstra (minimize max edge)
▸
1effort[*] = ∞; effort[0][0] = 0
2pq = {(0, (0,0))}
3while pq not empty:
4    (e, cell) = pop min effort
5    if cell settled: skip; mark settled
6    if cell == target: return e
7    for each neighbour:
8        cand = max(e, |Δheight|)
9        if cand < effort[nbr]: update; push
state
  • size3 × 3
  • start(0,0)
  • target(2,2)

line 1Travel from the top-left (0,0) to the bottom-right (2,2). A path's "effort" is the LARGEST absolute height difference between any two consecutive cells on it. We want the path whose largest step is as small as possible. Re-frame: give each cell a cost = the minimum possible max-step to reach it, then run Dijkstra — the priority queue always pops the lowest-effort cell, and edge "weight" = max(current effort, |height diff|).