LeetCode · #1631

Path With Minimum Effort Solution

Find a path from the top-left to the bottom-right that minimizes the maximum absolute height difference on any single step.

Section One · Problem

Problem Statement

🏷️

Difficulty

Medium

🔗

LeetCode

Problem #1631

🏗️

Pattern

Dijkstra with modified relaxation

The cost of a path is not the sum of its edges. Instead, it is the largest single climb or drop along that path. So the right state is: effort[r][c] = minimum possible max-edge cost to reach cell (r,c).

Example

Input:  heights = [[1,2,2],[3,8,2],[5,3,5]]
Output: 2
// A best path can keep every step difference ≤ 2.

Section Two · Approach 1

Explore All Paths — Exponential

A naive solution is to DFS through all possible grid paths, compute the maximum edge difference along each, and keep the minimum among them.

Why it works

If you examine every possible route, the best route by definition gives the minimum effort.

Problem: Grid path counts explode combinatorially. More importantly, once we know a better way to reach a cell with effort x, any later route reaching that same cell with effort y ≥ x is never useful. That is exactly the type of dominance rule Dijkstra exploits.

Section Three · Approach 2

Grid Dijkstra with Max-Edge Relaxation — O(m·n log(m·n))

Use a min-heap ordered by current path effort. When moving from (r,c) to neighbor (nr,nc), the new path effort is:

newEffort = max(currentEffort, abs(heights[r][c] - heights[nr][nc]))

If this beats the previously known best effort for that neighbor, update and push it into the heap.

💡 Mental model: Dijkstra normally accumulates sums. Here, instead of asking “what is the total cost so far?”, we ask “what is the worst step so far?” Every path carries its current worst jump, and we greedily expand the smallest such worst jump first.

Initialize effort[0][0] = 0.
Pop the cell with smallest known effort from the min-heap.
Skip stale entries where the heap value is worse than effort[r][c].
Relax each 4-direction neighbor using max(current, edgeCost).
The first time the destination is popped, its answer is finalized.

Equivalent alternative:

Binary search on the answer + BFS/DFS feasibility check also works.
But the Dijkstra version maps directly to the shortest-path concept page and is usually the cleanest single-pass explanation.

Section Four · Trace

Visual Walkthrough

Trace the example matrix.

Path With Minimum Effort — Dijkstra state

Section Five · Implementation

Code — Java & Python

Java — Dijkstra on grid

import java.util.*;

class Solution {
    private static final int[][] DIRS = {{1,0}, {-1,0}, {0,1}, {0,-1}};

    public int minimumEffortPath(int[][] heights) {
        int rows = heights.length, cols = heights[0].length;
        int[][] effort = new int[rows][cols];
        for (int[] row : effort) Arrays.fill(row, Integer.MAX_VALUE);
        effort[0][0] = 0;

        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[0] - b[0]);
        pq.offer(new int[] { 0, 0, 0 }); // effort, row, col

        while (!pq.isEmpty()) {
            int[] cur = pq.poll();
            int curEffort = cur[0], r = cur[1], c = cur[2];
            if (curEffort != effort[r][c]) continue;
            if (r == rows - 1 && c == cols - 1) return curEffort;

            for (int[] d : DIRS) {
                int nr = r + d[0], nc = c + d[1];
                if (nr < 0 || nr >= rows || nc < 0 || nc >= cols) continue;
                int edge = Math.abs(heights[r][c] - heights[nr][nc]);
                int nextEffort = Math.max(curEffort, edge);
                if (nextEffort < effort[nr][nc]) {
                    effort[nr][nc] = nextEffort;
                    pq.offer(new int[] { nextEffort, nr, nc });
                }
            }
        }

        return 0;
    }
}

Python — modified relaxation

import heapq

class Solution:
    def minimumEffortPath(self, heights: list[list[int]]) -> int:
        rows, cols = len(heights), len(heights[0])
        effort = [[float('inf')] * cols for _ in range(rows)]
        effort[0][0] = 0
        heap = [(0, 0, 0)]
        dirs = [(1, 0), (-1, 0), (0, 1), (0, -1)]

        while heap:
            cur_effort, r, c = heapq.heappop(heap)
            if cur_effort != effort[r][c]:
                continue
            if r == rows - 1 and c == cols - 1:
                return cur_effort

            for dr, dc in dirs:
                nr, nc = r + dr, c + dc
                if 0 <= nr < rows and 0 <= nc < cols:
                    edge = abs(heights[r][c] - heights[nr][nc])
                    next_effort = max(cur_effort, edge)
                    if next_effort < effort[nr][nc]:
                        effort[nr][nc] = next_effort
                        heapq.heappush(heap, (next_effort, nr, nc))

        return 0

Section Six · Analysis

Complexity Analysis

Approach	Time	Space	Trade-off
DFS over all routes	Exponential	O(m · n) recursion	Far too much recomputation.
Dijkstra ← optimal	O(m·n log(m·n))	O(m·n)	Each cell maintains its best known minimax effort and is improved only when a better frontier reaches it.

Section Seven · Edge Cases

Edge Cases & Pitfalls

Case	Expected behavior	Why it matters
Single cell	Return `0`	No edge is traversed.
Flat grid	Return `0`	Every edge difference is zero.
Large jump late in path	That jump sets the path effort	Path cost is the maximum edge, not the sum.
Using sum relaxation	Wrong answer	This is not ordinary shortest-sum path.
Heap stale entries	Skip them	Multiple heap entries per cell are normal.

⚠ Common Mistake: Writing next = cur + edge like standard Dijkstra. That solves a different problem: minimum total climb, not minimum worst step. The correct relaxation is max(cur, edge).

← Back to Shortest Path

LearningTree

LC 1631 · Path With Minimum Effort — Solution & Explanation | DSA Guide