Path With Minimum Effort (LeetCode 1631)
You're hiking across a rows x columns height map heights, where heights[row][col] is the elevation of that cell. Starting at (0, 0) and moving up/down/left/right, plan a route to the opposite corner at heights[rows - 1][columns - 1] that minimizes its effort.
A route's effort is defined as the single largest absolute height jump between two consecutive cells anywhere along it — not the sum of all the jumps.
Return the minimum effort achievable over any such route.
Worked Examples
heights = [[1,2,2],[3,8,2],[5,3,5]]2heights = [[1,2,3],[3,8,4],[5,3,5]]1heights = [[1,2,1,1,1],[1,2,1,2,1],[1,2,1,2,1],[1,2,1,2,1],[1,1,1,2,1]]0⚖️Formal Constraints & Bounds
rows == heights.lengthcolumns == heights[i].length1 <= rows, columns <= 1001 <= rows * columns <= 1040 <= heights[i][j] <= 106
Core Insight
Replacing Dijkstra's additive relaxation (dist[u] + weight) with a max relaxation (max(dist[u], weight)) is monotonic non-decreasing along any path, which is exactly the property Dijkstra's greedy min-heap correctness proof relies on -- so the algorithm carries over unchanged, just with a different combining operator.
Real-World Scenario & Production Applications
Route planning where the binding constraint is the single worst leg of the journey, not the cumulative cost — hiking trail difficulty, truck routing limited by the worst road grade on the route, or network paths bounded by the single slowest/lossiest hop rather than total latency.
Subproblems & Recurrence Decomposition3 Phases
Initialize a dist grid to infinity everywhere except the start, and seed a min-heap with (effort=0, 0, 0) -- the heap is ordered by the smallest bottleneck-so-far, not by cumulative cost.
dist = [[float("inf")] * cols for _ in range(rows)]
dist[0][0] = 0
min_heap = [(0, 0, 0)]Step-by-Step Execution Trace Table
Step-by-Step Minimax Relaxation Trace (heights = [[1,2,2],[3,8,2],[5,3,5]])
| Step | Popped Cell (r, c) | Effort | Neighbor Examined | Step Cost |Δh| | new_effort = max(effort, step) | Relaxed? | Resulting dist update |
|---|---|---|---|---|---|---|---|
| 1 | (0, 0) | 0 | (0, 1) h=2 | 1 | 1 | Yes | dist[0][1] = 1 |
| 1 | (0, 0) | 0 | (1, 0) h=3 | 2 | 2 | Yes | dist[1][0] = 2 |
| 2 | (0, 1) | 1 | (0, 2) h=2 | 0 | 1 | Yes | dist[0][2] = 1 |
| 2 | (0, 1) | 1 | (1, 1) h=8 | 6 | 6 | Yes | dist[1][1] = 6 |
| 3 | (0, 2) | 1 | (1, 2) h=2 | 0 | 1 | Yes | dist[1][2] = 1 |
| 4 | (1, 2) | 1 | (2, 2) h=5 | 3 | 3 | Yes | dist[2][2] = 3 |
| 5 | (1, 0) | 2 | (2, 0) h=5 | 2 | 2 | Yes | dist[2][0] = 2 |
| 6 | (2, 0) | 2 | (2, 1) h=3 | 2 | 2 | Yes | dist[2][1] = 2 |
| 7 | (2, 1) | 2 | (2, 2) h=5 | 2 | 2 | Yes! (2 < 3) | dist[2][2] = 2 -- destination popped next with effort 2 |
heights = [[1,2,2],[3,8,2],[5,3,5]]2Step-by-Step Minimax Relaxation Trace (heights = [[1,2,2],[3,8,2],[5,3,5]])
| Step | Popped Cell (r, c) | Effort | Neighbor Examined | Step Cost |Δh| | new_effort = max(effort, step) | Relaxed? | Resulting dist update |
|---|---|---|---|---|---|---|---|
| 1 | (0, 0) | 0 | (0, 1) h=2 | 1 | 1 | Yes | dist[0][1] = 1 |
| 1 | (0, 0) | 0 | (1, 0) h=3 | 2 | 2 | Yes | dist[1][0] = 2 |
| 2 | (0, 1) | 1 | (0, 2) h=2 | 0 | 1 | Yes | dist[0][2] = 1 |
| 2 | (0, 1) | 1 | (1, 1) h=8 | 6 | 6 | Yes | dist[1][1] = 6 |
| 3 | (0, 2) | 1 | (1, 2) h=2 | 0 | 1 | Yes | dist[1][2] = 1 |
| 4 | (1, 2) | 1 | (2, 2) h=5 | 3 | 3 | Yes | dist[2][2] = 3 |
| 5 | (1, 0) | 2 | (2, 0) h=5 | 2 | 2 | Yes | dist[2][0] = 2 |
| 6 | (2, 0) | 2 | (2, 1) h=3 | 2 | 2 | Yes | dist[2][1] = 2 |
| 7 | (2, 1) | 2 | (2, 2) h=5 | 2 | 2 | Yes! (2 < 3) | dist[2][2] = 2 -- destination popped next with effort 2 |
| 1 | rows, cols = len(heights), len(heights[0]) |
| 2 | dist = [[inf] * cols for _ in range(rows)] |
| 3 | dist[0][0] = 0 |
| 4 | min_heap = [(0, 0, 0)] |
| 5 | while min_heap: |
| 6 | effort, r, c = heappop(min_heap) |
| 7 | if (r, c) == (rows - 1, cols - 1): |
| 8 | return effort |
| 9 | if effort > dist[r][c]: |
| 10 | continue |
| 11 | for each neighbor (nr, nc) inside the grid: |
| 12 | new_effort = max(effort, abs(heights[nr][nc] - heights[r][c])) |
| 13 | if new_effort < dist[nr][nc]: |
| 14 | dist[nr][nc] = new_effort |
| 15 | heappush(min_heap, (new_effort, nr, nc)) |
Conceptual Narrative
🧭 Conceptual Foundation & Pattern Intuition
Effort is defined as the maximum absolute height difference between consecutive cells along a route. This is a minimax path problem: minimize the maximum edge weight on the path. Dijkstra adapts naturally by tracking minimax effort: when traversing edge , the candidate effort is . Popping from the min-heap guarantees optimal minimax convergence in time.
🥾 The Analogy: A Hiking Trail With One Steep Climb
Imagine you're choosing between hiking trails to reach a summit. A trail's difficulty isn't the sum of every elevation change along it — a trail with fifty gentle 10-foot steps is easier than a trail with one steep 200-foot cliff, even though the gentle trail's steps add up to more total climbing. What matters is the single hardest step you'll ever have to take. To find the easiest possible trail, you greedily always take the next step that keeps your worst-step-so-far as small as possible — exactly what a min-heap ordered by "worst step so far" gives you directly, with no extra code.
🔑 The Key Idea in the Code
The relaxation step is max(effort, step_cost) instead of classic Dijkstra's effort + step_cost. Taking one more step can never make your worst step-so-far smaller — it can only match it (if the new step is gentler than your current worst) or exceed it (if the new step is the new worst). That monotonic non-decreasing property is exactly what lets a min-heap greedily finalize the cell with the smallest current bottleneck first, the same correctness argument that makes classic Dijkstra work.
Summing edge weights instead of bottleneck max: Accumulating path costs as a sum
d + abs(h1 - h2)instead of the minimax bottleneckmax(effort, abs(h1 - h2)). The problem asks for the minimum of the maximum absolute difference along a path.Premature termination on non-popped destination: Returning the effort the moment the destination coordinate
(rows - 1, cols - 1)is enqueued. In Dijkstra, a node's distance is only guaranteed minimal when it is popped from the heap.Unchecked stale cell re-exploration: Failing to maintain a 2D
effortsmatrix initialized to infinity. Re-exploring cells with higher or equal effort causes infinite loops or exponential TLE.Summing instead of maxing in a minimax relaxation (Path With Minimum Effort, Swim in Rising Water).
new_effort = effort + step_costanswers a completely different question thannew_effort = max(effort, step_cost). The moment a problem defines cost as "the worst single step," the relaxation operator must change from+tomax, or the algorithm silently computes the wrong quantity while still looking like valid Dijkstra code.Confusing node-weighted and edge-weighted bottlenecks (Path With Minimum Effort vs. Swim in Rising Water). Path With Minimum Effort's cost lives on the EDGE between two cells (
abs(heights[nr][nc] - heights[r][c])); Swim in Rising Water's cost lives ON the cell itself (grid[r][c]). Using an edge-difference formula for Swim in Rising Water, or vice versa, produces a plausible-looking but wrong answer.
4-Phase Thought Process Model
Pattern Recognition Signals
The 10-second spot
Path cost is defined as the MAXIMUM of a sequence of per-step values, not the sum + grid with 4-directional moves.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
Invariant: since new_effort = max(effort, step_cost) is monotonic non-decreasing, the min-heap can still greedily finalize the cell with the smallest bottleneck-so-far first, exactly like classic Dijkstra.
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
Forgetting the
if effort > dist[r][c]: continuestale-entry check, since a cell can be pushed onto the heap multiple times before its cheapest entry is popped.
The 60-Second Interview Pitch
Say this out loud before you type a single line
"I run a Dijkstra variant where the relaxation rule is max(effort, abs(height_diff)) instead of a sum. A min-heap always pops the cell with the smallest current bottleneck, and because max() is monotonic non-decreasing along any path, the same greedy correctness argument that makes Dijkstra work still holds. I return the effort the moment the bottom-right cell is popped. Runs in O(M * N * log(M * N)) time."
Complexity & Mathematical Proof
O(M · N log(M · N))
Look at the execution steps: each of the MN cells can be pushed onto the min-heap up to 4 times (once per neighbor relaxation), and each heap push/pop costs O(log(MN)), giving O(M · N · log(M · N)) total.
O(M · N) Auxiliary
Look at memory allocations: Call stack uses O(1) Iterative. The dist table is O(M · N), and the min-heap holds at most O(M · N) entries.
T(M, N) = O(M · N log(M · N))
Derivation Progression
O(log(M · N))
Each pop removes the cell with the smallest bottleneck-so-far from a heap of size up to O(M · N).
4 · O(log(M · N)) per cell
Each of the up to 4 neighbors may be relaxed and pushed, each push costing O(log(M · N)).
(M · N) · O(log(M · N)) = O(M · N log(M · N))
Every cell is finalized (popped) at most once, each with O(log(M · N)) heap overhead.
Variable Definitions
Total number of rows in the grid
Total number of columns in the grid
Memory Architecture & Bounds
O(1) Iterative
O(M · N) dist table and min-heap entries
O(1) Minimum effort integer
Boundary Best / Worst Cases
Graph & Tree Traversal Frontier
Senior SWE Deconstruction & Hardware Caveats
Triggers: "minimum effort required", "maximum absolute difference in heights between consecutive cells". Minimax bottleneck path: minimize the maximum edge weight. A Senior SWE applies Modified Dijkstra with Minimax Relaxation.
. Time budget: runs in ms.
Target early return: return effort the moment is popped from the heap.
Path With Minimum Effort (LeetCode 1631)
You're hiking across a rows x columns height map heights, where heights[row][col] is the elevation of that cell. Starting at (0, 0) and moving up/down/left/right, plan a route to the opposite corner at heights[rows - 1][columns - 1] that minimizes its effort.
A route's effort is defined as the single largest absolute height jump between two consecutive cells anywhere along it — not the sum of all the jumps.
Return the minimum effort achievable over any such route.
Worked Examples
heights = [[1,2,2],[3,8,2],[5,3,5]]2heights = [[1,2,3],[3,8,4],[5,3,5]]1heights = [[1,2,1,1,1],[1,2,1,2,1],[1,2,1,2,1],[1,2,1,2,1],[1,1,1,2,1]]0⚖️Formal Constraints & Bounds
rows == heights.lengthcolumns == heights[i].length1 <= rows, columns <= 1001 <= rows * columns <= 1040 <= heights[i][j] <= 106
Core Insight
Replacing Dijkstra's additive relaxation (dist[u] + weight) with a max relaxation (max(dist[u], weight)) is monotonic non-decreasing along any path, which is exactly the property Dijkstra's greedy min-heap correctness proof relies on -- so the algorithm carries over unchanged, just with a different combining operator.
Real-World Scenario & Production Applications
Route planning where the binding constraint is the single worst leg of the journey, not the cumulative cost — hiking trail difficulty, truck routing limited by the worst road grade on the route, or network paths bounded by the single slowest/lossiest hop rather than total latency.
Subproblems & Recurrence Decomposition3 Phases
Initialize a dist grid to infinity everywhere except the start, and seed a min-heap with (effort=0, 0, 0) -- the heap is ordered by the smallest bottleneck-so-far, not by cumulative cost.
dist = [[float("inf")] * cols for _ in range(rows)]
dist[0][0] = 0
min_heap = [(0, 0, 0)]Step-by-Step Execution Trace Table
Step-by-Step Minimax Relaxation Trace (heights = [[1,2,2],[3,8,2],[5,3,5]])
| Step | Popped Cell (r, c) | Effort | Neighbor Examined | Step Cost |Δh| | new_effort = max(effort, step) | Relaxed? | Resulting dist update |
|---|---|---|---|---|---|---|---|
| 1 | (0, 0) | 0 | (0, 1) h=2 | 1 | 1 | Yes | dist[0][1] = 1 |
| 1 | (0, 0) | 0 | (1, 0) h=3 | 2 | 2 | Yes | dist[1][0] = 2 |
| 2 | (0, 1) | 1 | (0, 2) h=2 | 0 | 1 | Yes | dist[0][2] = 1 |
| 2 | (0, 1) | 1 | (1, 1) h=8 | 6 | 6 | Yes | dist[1][1] = 6 |
| 3 | (0, 2) | 1 | (1, 2) h=2 | 0 | 1 | Yes | dist[1][2] = 1 |
| 4 | (1, 2) | 1 | (2, 2) h=5 | 3 | 3 | Yes | dist[2][2] = 3 |
| 5 | (1, 0) | 2 | (2, 0) h=5 | 2 | 2 | Yes | dist[2][0] = 2 |
| 6 | (2, 0) | 2 | (2, 1) h=3 | 2 | 2 | Yes | dist[2][1] = 2 |
| 7 | (2, 1) | 2 | (2, 2) h=5 | 2 | 2 | Yes! (2 < 3) | dist[2][2] = 2 -- destination popped next with effort 2 |
heights = [[1,2,2],[3,8,2],[5,3,5]]2Step-by-Step Minimax Relaxation Trace (heights = [[1,2,2],[3,8,2],[5,3,5]])
| Step | Popped Cell (r, c) | Effort | Neighbor Examined | Step Cost |Δh| | new_effort = max(effort, step) | Relaxed? | Resulting dist update |
|---|---|---|---|---|---|---|---|
| 1 | (0, 0) | 0 | (0, 1) h=2 | 1 | 1 | Yes | dist[0][1] = 1 |
| 1 | (0, 0) | 0 | (1, 0) h=3 | 2 | 2 | Yes | dist[1][0] = 2 |
| 2 | (0, 1) | 1 | (0, 2) h=2 | 0 | 1 | Yes | dist[0][2] = 1 |
| 2 | (0, 1) | 1 | (1, 1) h=8 | 6 | 6 | Yes | dist[1][1] = 6 |
| 3 | (0, 2) | 1 | (1, 2) h=2 | 0 | 1 | Yes | dist[1][2] = 1 |
| 4 | (1, 2) | 1 | (2, 2) h=5 | 3 | 3 | Yes | dist[2][2] = 3 |
| 5 | (1, 0) | 2 | (2, 0) h=5 | 2 | 2 | Yes | dist[2][0] = 2 |
| 6 | (2, 0) | 2 | (2, 1) h=3 | 2 | 2 | Yes | dist[2][1] = 2 |
| 7 | (2, 1) | 2 | (2, 2) h=5 | 2 | 2 | Yes! (2 < 3) | dist[2][2] = 2 -- destination popped next with effort 2 |
| 1 | rows, cols = len(heights), len(heights[0]) |
| 2 | dist = [[inf] * cols for _ in range(rows)] |
| 3 | dist[0][0] = 0 |
| 4 | min_heap = [(0, 0, 0)] |
| 5 | while min_heap: |
| 6 | effort, r, c = heappop(min_heap) |
| 7 | if (r, c) == (rows - 1, cols - 1): |
| 8 | return effort |
| 9 | if effort > dist[r][c]: |
| 10 | continue |
| 11 | for each neighbor (nr, nc) inside the grid: |
| 12 | new_effort = max(effort, abs(heights[nr][nc] - heights[r][c])) |
| 13 | if new_effort < dist[nr][nc]: |
| 14 | dist[nr][nc] = new_effort |
| 15 | heappush(min_heap, (new_effort, nr, nc)) |
Conceptual Narrative
🧭 Conceptual Foundation & Pattern Intuition
Effort is defined as the maximum absolute height difference between consecutive cells along a route. This is a minimax path problem: minimize the maximum edge weight on the path. Dijkstra adapts naturally by tracking minimax effort: when traversing edge , the candidate effort is . Popping from the min-heap guarantees optimal minimax convergence in time.
🥾 The Analogy: A Hiking Trail With One Steep Climb
Imagine you're choosing between hiking trails to reach a summit. A trail's difficulty isn't the sum of every elevation change along it — a trail with fifty gentle 10-foot steps is easier than a trail with one steep 200-foot cliff, even though the gentle trail's steps add up to more total climbing. What matters is the single hardest step you'll ever have to take. To find the easiest possible trail, you greedily always take the next step that keeps your worst-step-so-far as small as possible — exactly what a min-heap ordered by "worst step so far" gives you directly, with no extra code.
🔑 The Key Idea in the Code
The relaxation step is max(effort, step_cost) instead of classic Dijkstra's effort + step_cost. Taking one more step can never make your worst step-so-far smaller — it can only match it (if the new step is gentler than your current worst) or exceed it (if the new step is the new worst). That monotonic non-decreasing property is exactly what lets a min-heap greedily finalize the cell with the smallest current bottleneck first, the same correctness argument that makes classic Dijkstra work.
Summing edge weights instead of bottleneck max: Accumulating path costs as a sum
d + abs(h1 - h2)instead of the minimax bottleneckmax(effort, abs(h1 - h2)). The problem asks for the minimum of the maximum absolute difference along a path.Premature termination on non-popped destination: Returning the effort the moment the destination coordinate
(rows - 1, cols - 1)is enqueued. In Dijkstra, a node's distance is only guaranteed minimal when it is popped from the heap.Unchecked stale cell re-exploration: Failing to maintain a 2D
effortsmatrix initialized to infinity. Re-exploring cells with higher or equal effort causes infinite loops or exponential TLE.Summing instead of maxing in a minimax relaxation (Path With Minimum Effort, Swim in Rising Water).
new_effort = effort + step_costanswers a completely different question thannew_effort = max(effort, step_cost). The moment a problem defines cost as "the worst single step," the relaxation operator must change from+tomax, or the algorithm silently computes the wrong quantity while still looking like valid Dijkstra code.Confusing node-weighted and edge-weighted bottlenecks (Path With Minimum Effort vs. Swim in Rising Water). Path With Minimum Effort's cost lives on the EDGE between two cells (
abs(heights[nr][nc] - heights[r][c])); Swim in Rising Water's cost lives ON the cell itself (grid[r][c]). Using an edge-difference formula for Swim in Rising Water, or vice versa, produces a plausible-looking but wrong answer.
4-Phase Thought Process Model
Pattern Recognition Signals
The 10-second spot
Path cost is defined as the MAXIMUM of a sequence of per-step values, not the sum + grid with 4-directional moves.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
Invariant: since new_effort = max(effort, step_cost) is monotonic non-decreasing, the min-heap can still greedily finalize the cell with the smallest bottleneck-so-far first, exactly like classic Dijkstra.
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
Forgetting the
if effort > dist[r][c]: continuestale-entry check, since a cell can be pushed onto the heap multiple times before its cheapest entry is popped.
The 60-Second Interview Pitch
Say this out loud before you type a single line
"I run a Dijkstra variant where the relaxation rule is max(effort, abs(height_diff)) instead of a sum. A min-heap always pops the cell with the smallest current bottleneck, and because max() is monotonic non-decreasing along any path, the same greedy correctness argument that makes Dijkstra work still holds. I return the effort the moment the bottom-right cell is popped. Runs in O(M * N * log(M * N)) time."
Complexity & Mathematical Proof
O(M · N log(M · N))
Look at the execution steps: each of the MN cells can be pushed onto the min-heap up to 4 times (once per neighbor relaxation), and each heap push/pop costs O(log(MN)), giving O(M · N · log(M · N)) total.
O(M · N) Auxiliary
Look at memory allocations: Call stack uses O(1) Iterative. The dist table is O(M · N), and the min-heap holds at most O(M · N) entries.
T(M, N) = O(M · N log(M · N))
Derivation Progression
O(log(M · N))
Each pop removes the cell with the smallest bottleneck-so-far from a heap of size up to O(M · N).
4 · O(log(M · N)) per cell
Each of the up to 4 neighbors may be relaxed and pushed, each push costing O(log(M · N)).
(M · N) · O(log(M · N)) = O(M · N log(M · N))
Every cell is finalized (popped) at most once, each with O(log(M · N)) heap overhead.
Variable Definitions
Total number of rows in the grid
Total number of columns in the grid
Memory Architecture & Bounds
O(1) Iterative
O(M · N) dist table and min-heap entries
O(1) Minimum effort integer
Boundary Best / Worst Cases
Graph & Tree Traversal Frontier
Senior SWE Deconstruction & Hardware Caveats
Triggers: "minimum effort required", "maximum absolute difference in heights between consecutive cells". Minimax bottleneck path: minimize the maximum edge weight. A Senior SWE applies Modified Dijkstra with Minimax Relaxation.
. Time budget: runs in ms.
Target early return: return effort the moment is popped from the heap.