← DSA Atlas
Dedicated problem page · #1631

Path With Minimum Effort

MediumShortest Path, Dijkstra and Minimum Spanning TreeDijkstra (minimize maximum edge)Min-heap where path cost is the bottleneck (max step)
Solve on LeetCode ↗
1631
MediumShortest Path, Dijkstra and Minimum Spanning TreeMin-heap where path cost is the bottleneck (max step)Dijkstra (minimize maximum edge)

Path With Minimum Effort

Given a rows x cols grid of heights, you start at the top-left cell and want to reach the bottom-right cell moving up/down/left/right. A route's effort is the maximum absolute height difference between two consecutive cells along it. Return the minimum effort over all routes.

Open official problem prompt ↗
In plain English

Find a top-left to bottom-right route whose single hardest climb (largest height jump) is as small as possible.

Picture it like this

A hiker crossing terrain cares only about the steepest single step they must take, not the total elevation change; they seek the route with the gentlest worst step.

Example
Input
heights = [[1,2,2],[3,8,2],[5,3,5]]
Output
2
Why
The route along the top row then the right column keeps every step's height difference at most 2, and no route can guarantee a smaller maximum step.
Constraints
rows == heights.lengthcols == heights[0].length1 <= rows, cols <= 1001 <= heights[i][j] <= 10^6
Pattern lesson

See the pattern, then code

Dijkstra (minimize maximum edge)
Recognition clue

You minimize the largest single step along a path rather than the sum - a minimum-bottleneck path, solvable with Dijkstra where 'distance' is the running max.

↗
Shortest Path, Dijkstra and Minimum Spanning Tree

Shortest paths with non-negative weights or minimum-cost graph connection.. Replace additive relaxation with max: the cost to reach a neighbor is max(current effort, height difference). Dijkstra still works because that combined cost never decreases along a path.

New words, made simpleKnow these before the algorithm
Bottleneck path
A path scored by its single worst (largest) edge rather than the sum of edges.
Effort
The maximum absolute height difference between adjacent cells along a route.
Monotone cost
Extending a path can only keep or raise the running max, never lower it - the property Dijkstra needs.
Approaches from first idea to best ideaCompare the trade-offs
ApproachHow it thinksCost
Binary search on effort + BFS/DFS

Correct and clean; a different framing that is equally acceptable.

Guess a threshold T and check reachability using only steps <= T, binary search the smallest feasible T.

Time O(R*C log(maxH))Space O(R*C)
Best choiceDijkstra with max-relaxation

Single pass, no threshold guessing, directly returns the answer.

Treat each cell as a node and relax neighbors using max(effort, diff) with a min-heap.

Time O(R*C log(R*C))Space O(R*C)
The rule we keep true

Invariant

When a cell is popped, effort[cell] equals the minimum achievable bottleneck effort from the start to that cell.

Why this is correct

Reasoning

The path cost max(...) is non-decreasing as the path grows, exactly like non-negative additive weights are non-decreasing. That monotonicity means the first time Dijkstra settles a cell it has the optimal bottleneck value, so the destination's popped effort is the answer.

The algorithm in three movesSay these aloud before coding
1Keep effort[r][c] = smallest possible max-step to reach that cell, starting 0 at the origin

effort[0][0]=0, pop (0,0,0)

2Pop the cell with the smallest effort from a min-heap

right steps diff 1 then 0 -> effort=1 at (0,2)

3Return its effort if it is the destination

down diffs to reach (2,2) keep max=2

4For each neighbor compute ne = max(current effort, |height difference|); if it improves effort[neighbor], update and push

pop (2,2,2) -> return 2

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example
10
21
22
33
84
25
56
37
58
1 · Read(0,0) height 1
2 · Askseed
3 · Update stateeffort[0][0]=0
4 · ResultPop origin.
Key takeaway

Dijkstra over the grid tracks the minimum possible bottleneck step to each cell until the bottom-right is popped.

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

  1. 1
    Lines 4-7Effort grid and heap

    effort holds the best bottleneck per cell; the heap is seeded at the origin with effort 0.

  2. 2
    Lines 9-13Pop, early return, stale skip

    The destination pop returns immediately; a popped effort worse than the recorded one is stale and skipped.

  3. 3
    Lines 14-21Max-relaxation of neighbors

    ne = max(current effort, |height diff|); push only when it beats the neighbor's stored effort.

Make it stick

Edge cases, mistakes, and one self-check

E

Edge cases to test

  • A 1x1 grid has effort 0 (already at the destination)
  • A single row or column forces one path and its bottleneck
  • A flat grid of equal heights gives effort 0
!

Common beginner mistakes

  • Adding differences instead of taking the max, which solves the wrong problem
  • Forgetting the four-directional moves include up and left, not just right and down
  • Omitting the stale-entry skip and re-expanding cells needlessly
Check your understanding

Why can standard Dijkstra be adapted by simply swapping sum for max?

More in Shortest Path, Dijkstra and Minimum Spanning Tree

#743Network Delay TimeSingle-source shortest path#332Reconstruct ItineraryEulerian path (Hierholzer's algorithm)#505The Maze IIWeighted shortest path on a grid#778Swim in Rising WaterMinimize the maximum along a path (minimax path)#787Cheapest Flights Within K StopsShortest path with a hop limit#815Bus RoutesUnweighted shortest path (fewest transfers)