Path With Minimum Effort
Path With Minimum Effort is LeetCode 1631 (Medium). You are given a grid heights with rows × columns cells, where heights[r][c] is the height of that cell. You start at the top-left cell and want to reach the bottom-right cell.
- From any cell you may move up, down, left or right to a neighbouring cell.
- A move costs the absolute difference between the two heights.
- The effort of a route is the largest single move cost along it, not the sum.
Return the minimum effort needed to travel from the top-left to the bottom-right.
- rows == heights.length
- columns == heights[i].length
- 1 <= rows, columns <= 100
- 1 <= heights[i][j] <= 10⁶
Intuition
Effort is the steepest step you are forced to take, so a long, gentle detour beats a short route with one cliff in it.
That is a shortest-path problem where cost combines differently. In plain Dijkstra, extending a path by an edge adds its weight; here a step of cost s turns the effort into max(effort, s). Dijkstra only needs one property to stay correct: a path never gets cheaper as it grows. A running maximum has that property just like a sum of non-negative weights, so the first time the bottom-right cell leaves the heap, no waiting route can beat it.
Minimise the maximum along a path, as in the path with minimum effort LeetCode problem, is a bottleneck path problem. When the path can move in any direction, reach for a modified Dijkstra (push max(effort, step) instead of effort + step), or for binary search on the answer with a reachability check. Union-find over the edges sorted by cost also works: the answer is the edge that first joins the two corners. The same shape appears in Swim in Rising Water, where the cost is the highest cell rather than the steepest step.
Approach
Before reading on, decide what number the heap stores for each cell and what replaces the + in Dijkstra's relaxation. Aim for O(m·n·log(m·n)) time.
Two ways to solve it
Pop the cell with the smallest effort so far and relax its neighbours with max(effort, step).
- One pass: each cell settles once.
- Early exit: stops when the corner is popped.
- Watch out: skip stale heap entries.
The usual interview answer.
Guess a limit and check with BFS whether the corner is reachable using only steps within it.
- Simple parts: a plain BFS and a binary search.
- Monotonic: a larger limit never hurts.
- Cost: about 20 full BFS runs for heights up to 10⁶.
Good when a heap feels heavy.
Dijkstra settles each cell once and stops as soon as the corner is final, so it is the one to learn first. The steps, code and live demo follow Dijkstra; the binary search code comes after the demo.
Store the best effort per cell
dist[r][c] = the smallest effort of any route found so far from the start to (r, c). Set every cell to infinity except the start, which is 0 because no step has been taken. Push (0, 0, 0) onto a min-heap.
Pop the smallest effort
Pop (effort, r, c). If it is the bottom-right cell, return effort: it is the smallest effort any route can reach it with. If effort > dist[r][c], this is an old entry left behind after a cheaper route was found; skip it.
Relax with max instead of plus
For each neighbour, step = |heights[nr][nc] - heights[r][c]| and new_effort = max(effort, step). If new_effort < dist[nr][nc], record it and push the neighbour. A neighbour can be pushed several times as better routes appear; the stale-entry check keeps the extra copies cheap.
Path With Minimum Effort solution in Python | C++ | Java
dist holds the smallest effort found so far to reach each cell. The start needs no step, so it is 0 and goes on the heap; every other cell is ∞.dist holds the smallest effort found so far to reach each cell. The start needs no step, so it is 0 and goes on the heap; every other cell is ∞.Binary search on the effort with BFS
Binary search over the effort limit from 0 to 10⁶. For each guess, BFS from the top-left using only steps whose height difference is within the limit; if the bottom-right is reached, try a smaller limit, otherwise a larger one.
Common pitfalls
Adding step costs instead of taking the maximum
new_effort = effort + abs(heights[nr][nc] - heights[r][c])
new_effort = max(effort, abs(heights[nr][nc] - heights[r][c]))
That is ordinary Dijkstra and returns the least total climb. On the first sample it returns 4 (the route through 1, 2, 2, 2, 5 climbs 1+0+0+3) instead of 2, because it prefers a short route with one steep step over a longer, flatter one.
Filling a DP table that only moves right and down
f[r][c] = min(max(f[r-1][c], up_step), max(f[r][c-1], left_step))
# no fixed fill order exists: let a min-heap pick the next cell (Dijkstra)
On [[1,2,3],[8,7,5],[6,4,1]] the best route snakes right, then back left along the middle row, then right again, for effort 3. A right/down DP never considers a left move and returns 4.
Returning when the destination is pushed, not popped
if new_effort < dist[nr][nc]:
if (nr, nc) == (m - 1, n - 1):
return new_efforteffort, r, c = heapq.heappop(heap)
if r == m - 1 and c == n - 1:
return effortThe first route to reach a cell is not necessarily the best one. In the 2×2 demo the corner is first pushed with effort 4, and only later lowered to 3. A cell's effort is final only when it comes off the heap.
Edge cases
The start is the destination, so the first pop returns 0. The destination check comes before the neighbour loop, so no special case is needed.
Complexity
Path With Minimum Effort vs similar grid path problems
All three go from the top-left to the bottom-right of a grid. What a path costs decides the tool.
| Problem | Cost of a path | Moves | Standard method |
|---|---|---|---|
| Minimum Path Sum (64) | Sum of the cells | Right and down only | DP in row order |
| Path With Minimum Effort (1631) | Largest height difference between steps | All 4 directions | Dijkstra with max, or binary search + BFS |
| Swim in Rising Water (778) | Highest cell on the path | All 4 directions | Dijkstra with max, or binary search + BFS |
Path With Minimum Effort FAQ
What does a path with minimum effort Python solution look like?
Use heapq with tuples (effort, r, c), so the heap orders by effort first. Keep a dist grid of float("inf"), pop until the bottom-right cell appears, skip entries whose effort exceeds dist, and push neighbours with max(effort, step) when that beats their dist.