Topics › Graphs › Shortest Path Algorithms and Problems

Path with minimum effort

Hard TUF ID 525 A2Z

LeetCode ↗ Java source ↗ Edit this article ↗

Problem

You are a hiker on a grid heights of rows × cols cells, where heights[r][c] is the height of a cell. You start at the top-left cell (0, 0) and must reach the bottom-right cell (rows - 1, cols - 1), 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 minimum effort over all routes.

Constraints: 1 ≤ rows, cols ≤ 100, 1 ≤ heights[r][c] ≤ 10^6.

Example 1

heights = 1 2 2
          3 8 2
          5 3 5
answer = 2               // route 1 → 3 → 5 → 3 → 5 has steps 2, 2, 2, 2

Example 2

heights = 1 2 3
          3 8 4
          5 3 5
answer = 1               // route 1 → 2 → 3 → 4 → 5 has every step equal to 1

The important word is largest. The cost of a route is not the sum of its steps but its single worst step, so a long, gentle detour beats a short route with one cliff. The test [[1, 100], [2, 3]] has answer 1: going right first costs 99, going down first costs 1.

All approaches use the same four-direction offsets:

static final int[] DR = {-1, 0, 1, 0}, DC = {0, 1, 0, -1};

Approach 1: Brute force, try every route

Intuition. Enumerate every route that never revisits a cell, track the worst step seen so far, and keep the minimum over routes that reach the target. Backtracking does exactly this: mark a cell when you enter it, unmark it when you leave. Prune any partial route whose effort already matches or exceeds the best complete one; extending it can only keep or raise its effort, never lower it.

Algorithm.

Start walk at (0, 0) with effort 0.
If effort ≥ best, stop. If at the target, set best = effort.
Mark the cell, recurse into every unmarked neighbour with max(effort, |step|), unmark.

static int bruteForce(int[][] heights) {
    int[] best = {Integer.MAX_VALUE};
    walk(heights, 0, 0, 0, new boolean[heights.length][heights[0].length], best);
    return best[0];
}

static void walk(int[][] h, int r, int c, int effort, boolean[][] onPath, int[] best) {
    if (effort >= best[0]) return;                        // this path can no longer beat the best one
    if (r == h.length - 1 && c == h[0].length - 1) {
        best[0] = effort;
        return;
    }
    onPath[r][c] = true;
    for (int k = 0; k < 4; k++) {
        int nr = r + DR[k], nc = c + DC[k];
        if (nr >= 0 && nr < h.length && nc >= 0 && nc < h[0].length && !onPath[nr][nc]) {
            walk(h, nr, nc, Math.max(effort, Math.abs(h[nr][nc] - h[r][c])), onPath, best);
        }
    }
    onPath[r][c] = false;
}

Complexity. Exponential time: a 5 × 5 grid already has 8512 self-avoiding corner-to-corner routes, and the count grows explosively with size. Space O(rows × cols) for the marks and the recursion. Useful only as a reference on tiny grids.

Approach 2: Better, binary search on the answer

Intuition. Turn the optimisation into a yes/no question: “can I reach the target if no step may exceed limit?” That is plain reachability, a BFS that only uses steps with difference at most limit. The answer is monotonic: if a limit works, every larger limit also works, since the same route is still allowed. So binary search for the smallest limit that works.

The search range is 0 to max height − min height, because no step can differ by more than that.

Algorithm.

Set lo = 0, hi = max − min.
While lo < hi: let mid be the midpoint. If canReach(mid), set hi = mid; otherwise lo = mid + 1.
Return lo.

canReach(limit) is a BFS from (0, 0) that enters a neighbour only if it is unseen and the height difference is at most limit.

static int binarySearchBfs(int[][] heights) {
    int min = Integer.MAX_VALUE, max = Integer.MIN_VALUE;
    for (int[] row : heights) {
        for (int x : row) {
            min = Math.min(min, x);
            max = Math.max(max, x);
        }
    }
    int lo = 0, hi = max - min;                           // no single step can differ by more than max - min
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (canReach(heights, mid)) hi = mid;
        else lo = mid + 1;
    }
    return lo;
}

static boolean canReach(int[][] h, int limit) {
    int n = h.length, m = h[0].length;
    boolean[][] seen = new boolean[n][m];
    Deque<int[]> queue = new ArrayDeque<>();
    queue.add(new int[]{0, 0});
    seen[0][0] = true;
    while (!queue.isEmpty()) {
        int[] cell = queue.poll();
        int r = cell[0], c = cell[1];
        if (r == n - 1 && c == m - 1) return true;
        for (int k = 0; k < 4; k++) {
            int nr = r + DR[k], nc = c + DC[k];
            if (nr >= 0 && nr < n && nc >= 0 && nc < m && !seen[nr][nc]
                    && Math.abs(h[nr][nc] - h[r][c]) <= limit) {
                seen[nr][nc] = true;
                queue.add(new int[]{nr, nc});
            }
        }
    }
    return false;
}

Complexity. Time O(rows × cols × log H), where H ≤ 10^6 is the height range: about 20 BFS runs, each linear in the grid. Space O(rows × cols) for the seen grid and the queue.

Approach 3: Optimal, Dijkstra with “max” instead of “sum”

Intuition. This is a shortest-path problem with an unusual path cost. Dijkstra’s algorithm does not actually need the cost to be a sum. It needs one property: extending a route never makes it cheaper. With non-negative weights that holds for sums, and it holds for maximums too, since max(e, step) ≥ e. Under that property, the cheapest unfinished cell in the heap can never be improved later, because every other route to it is already at least as expensive and can only get worse. So the greedy “pop the cheapest” rule still works.

We keep effort[r][c], the smallest known effort to reach each cell, and a min-heap of {effort, row, col}. Relaxing a step from a cell with effort e to a neighbour gives max(e, |height difference|) instead of e + w. When the target is popped, its effort is final.

Algorithm.

Set effort[0][0] = 0, everything else infinity, and push {0, 0, 0}.
Pop the smallest entry. Skip it if stale. If it is the target, return its effort.
For each neighbour, compute next = max(e, |difference|). If it beats the neighbour’s effort, store it and push.

static int optimal(int[][] heights) {
    int n = heights.length, m = heights[0].length;
    int[][] effort = new int[n][m];
    for (int[] row : effort) Arrays.fill(row, Integer.MAX_VALUE);
    effort[0][0] = 0;
    PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> Integer.compare(a[0], b[0]));   // {effort, row, col}
    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 == n - 1 && c == m - 1) return e;           // first pop of the target is final
        for (int k = 0; k < 4; k++) {
            int nr = r + DR[k], nc = c + DC[k];
            if (nr < 0 || nr >= n || nc < 0 || nc >= m) continue;
            int next = Math.max(e, Math.abs(heights[nr][nc] - heights[r][c]));
            if (next < effort[nr][nc]) {
                effort[nr][nc] = next;
                pq.add(new int[]{next, nr, nc});
            }
        }
    }
    return effort[n - 1][m - 1];
}

Dry run on Example 1 (cells are (row, col)):

pop (effort, cell)	improvements pushed
(0, (0,0))	(1, (0,1)), (2, (1,0))
(1, (0,1))	(1, (0,2)), (6, (1,1))
(1, (0,2))	(1, (1,2))
(1, (1,2))	(3, (2,2))
(2, (1,0))	(5, (1,1)), (2, (2,0))
(2, (2,0))	(2, (2,1))
(2, (2,1))	(2, (2,2))
(2, (2,2))	target popped: return 2

The route along the right edge gives the target a tentative effort of 3 first, but that entry is still in the heap when the left-edge route lowers the target to 2. The (2, (2,2)) entry pops first and the answer is 2. The tall 8 in the middle is never used: its best effort is 5, and the algorithm finishes before popping it.

Complexity. Time O(rows × cols × log(rows × cols)): each cell is pushed at most four times and each heap operation costs a logarithm. Space O(rows × cols) for the effort grid and the heap. Unlike Approach 2, the running time does not depend on how large the heights are.

Edge cases and pitfalls

Single cell. Start equals target, no steps are taken, the effort is 0. All three methods return 0 for [[7]].
One row or one column. There is only one simple route, so the answer is its largest step: 9 for [[1, 10, 6, 7, 9, 10, 4, 9]].
Max, not sum. Using e + |difference| computes the total climb instead of the worst step. On Example 2 it returns 4 (the steps 1, 1, 1, 1 add up), while the correct effort is 1.
Absolute value. Going down hill is as costly as going up; use Math.abs.
Plain BFS is not enough. BFS minimises the number of steps, which is unrelated to the worst step.
Binary search bounds. Use hi = max − min and the lo + (hi − lo) / 2 midpoint; the loop condition lo < hi with hi = mid on success finds the smallest feasible limit.

Djisktra’s Algorithm is the sum-based original.
Why priority Queue is used in Djisktra’s Algorithm explains why popping the smallest entry first is what makes Approach 3 fast.
Shortest Distance in a Binary Maze is the grid case where every step costs the same and BFS suffices.
Swim in Rising Water minimises the maximum cell on a route, the same min-max idea.

Path with minimum effort

Problem

Approach 1: Brute force, try every route

Approach 2: Better, binary search on the answer

Approach 3: Optimal, Dijkstra with “max” instead of “sum”

Edge cases and pitfalls

Related problems