Path With Minimum Effort

MediumGraphs · Dijkstra (Minimax) · Binary Search🧩 Shortest Paths LeetCode #1631 ↗Updated Oct 30, 2026

Problem

A hiker stands on the top-left cell of a rows × cols grid heights and wants to reach the bottom-right cell, moving up, down, left or right. The effort of a route is the largest absolute height difference between two consecutive cells on it. Return the smallest possible effort of any route.

Inputheights=[[1,2,2],[3,8,2],[5,3,5]]Output2

Inputheights=[[1,2,3],[3,8,4],[5,3,5]]Output1

Inputheights=[[4]]Output0

1 ≤ rows, cols ≤ 100 · 1 ≤ heights[i][j] ≤ 10⁶

Try it yourself

Java

class Solution {
    public int minimumEffortPath(int[][] heights) {
        
    }
}

Your code is saved in this browser.Submit on LeetCode ↗

Key insight

The cost of a route is a max, not a sum — but extending a route can still only keep or raise its cost. That monotonicity is all Dijkstra needs: relax with max(effort[u], |h(u) − h(v)|) and pop the smallest effort first.

PatternShortest Paths

Instinct Weighted edges plus "minimum cost, time or effort to reach" - grab a min-heap and always expand the cheapest unsettled node next (Dijkstra).

Memory hack Pop the cheapest, skip the stale, relax the rest - Dijkstra is a ripple in a pond that touches near shores before far ones.

Open the Shortest Paths guide →

Approaches

Brute ForceRepeated Relaxation Until Stable

Time O((R·C)²)Space O(R·C)

Keep effort[cell], initially infinite except the start. Sweep the whole grid repeatedly, improving each neighbour with max(effort[cell], step), until a sweep changes nothing. Like Bellman-Ford, a best route has at most R·C cells, so the number of sweeps is bounded.

Java

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;
    int[][] dirs = { {1, 0}, {-1, 0}, {0, 1}, {0, -1} };
    boolean changed = true;
    while (changed) {
        changed = false;
        for (int r = 0; r < rows; r++) {
            for (int c = 0; c < cols; c++) {
                if (effort[r][c] == Integer.MAX_VALUE) continue;
                for (int[] d : dirs) {
                    int nr = r + d[0], nc = c + d[1];
                    if (nr < 0 || nc < 0 || nr >= rows || nc >= cols) continue;
                    int step = Math.abs(heights[nr][nc] - heights[r][c]);
                    int cand = Math.max(effort[r][c], step);
                    if (cand < effort[nr][nc]) {
                        effort[nr][nc] = cand;
                        changed = true;
                    }
                }
            }
        }
    }
    return effort[rows - 1][cols - 1];
}

Obviously correct, but may need a full grid sweep per cell of path length.

BetterBinary Search on the Answer + BFS

Time O(R·C · log H)Space O(R·C)

“Can we finish using only steps of size ≤ k?” is monotone in k: if yes for k, then yes for any larger value. Binary search the smallest such k in [0, maxHeight], using a plain BFS as the yes/no check.

Java

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

public int minimumEffortPath(int[][] heights) {
    int lo = 0, hi = 1_000_000;
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (canReach(heights, mid)) hi = mid; // mid works: try smaller
        else lo = mid + 1;
    }
    return lo;
}

private boolean canReach(int[][] h, int limit) {
    int rows = h.length, cols = h[0].length;
    boolean[][] seen = new boolean[rows][cols];
    Deque<int[]> queue = new ArrayDeque<>();
    queue.add(new int[]{0, 0});
    seen[0][0] = true;
    while (!queue.isEmpty()) {
        int[] cur = queue.poll();
        if (cur[0] == rows - 1 && cur[1] == cols - 1) return true;
        for (int[] d : DIRS) {
            int nr = cur[0] + d[0], nc = cur[1] + d[1];
            if (nr < 0 || nc < 0 || nr >= rows || nc >= cols || seen[nr][nc]) continue;
            if (Math.abs(h[nr][nc] - h[cur[0]][cur[1]]) > limit) continue;
            seen[nr][nc] = true;
            queue.add(new int[]{nr, nc});
        }
    }
    return false;
}

Simple BFS check, but repeats a full search ~20 times (log of 10⁶).

OptimalDijkstra on Max-Edge Cost

Time O(R·C · log(R·C))Space O(R·C)

Treat each cell as a node. Pop the cell with the smallest known effort from a min-heap; that value is final, because any detour can only keep or raise the max. Relax neighbours with max(effort, step) and return the moment the bottom-right cell is popped.

Java

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;
    int[][] dirs = { {1, 0}, {-1, 0}, {0, 1}, {0, -1} };
    // Heap entries: {effort, row, col}, smallest effort first
    PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> Integer.compare(a[0], b[0]));
    pq.add(new int[]{0, 0, 0});
    while (!pq.isEmpty()) {
        int[] top = pq.poll();
        int e = top[0], r = top[1], c = top[2];
        if (e > effort[r][c]) continue; // stale entry
        if (r == rows - 1 && c == cols - 1) return e;
        for (int[] d : dirs) {
            int nr = r + d[0], nc = c + d[1];
            if (nr < 0 || nc < 0 || nr >= rows || nc >= cols) continue;
            int cand = Math.max(e, Math.abs(heights[nr][nc] - heights[r][c]));
            if (cand < effort[nr][nc]) {
                effort[nr][nc] = cand;
                pq.add(new int[]{cand, nr, nc});
            }
        }
    }
    return 0; // unreachable: the grid is always connected
}

One search, no guessing range, and it stops as soon as the target is settled.

Pro tip

Another valid optimal: sort all adjacent-cell edges by difference and union them (Kruskal) until the two corners share a root — the last weight added is the answer.

At a glance

Level	Approach	Time	Space
Brute Force	Repeated Relaxation Until Stable	`O((R·C)²)`	`O(R·C)`
Better	Binary Search on the Answer + BFS	`O(R·C · log H)`	`O(R·C)`
Optimal	Dijkstra on Max-Edge Cost	`O(R·C · log(R·C))`	`O(R·C)`

Common pitfalls

Summing the differences — effort is the maximum single step, not the total.
Plain BFS/DFS without a priority — the first visit to a cell is not its best effort.
Forgetting the 1×1 grid — the answer is 0 with no steps at all.

Interview tips

Name the variant: “minimax path” — Dijkstra with max instead of +.
Offer binary search + BFS as an easier-to-code fallback and explain the monotonicity.
Mention the Kruskal / Union-Find alternative to show breadth.

Pattern

Minimax shortest path → minimise the worst edge on a route: Dijkstra with max, or binary search + BFS.

My notes saved in this browser