Command Palette

Search for a command to run...

Hectal
Problem 26.2 · Shortest PathsMedium

Path With Minimum Effort

PatternDijkstra's Shortest PathBinary Search on the AnswerUnion-Find

What it teaches: Minimax Dijkstra on a grid: a path's cost is its largest step.

Practise it on judges as “Path With Minimum Effort”.

The problem

Walk from the top-left to the bottom-right of a height grid (up/down/left/right). A route's effort is its largest absolute height difference between consecutive cells. Return the minimum effort.

Example 1

Input: heights = [[1,2,2],[3,8,2],[5,3,5]]
Output: 2

Constraints

  • 1 ≤ rows, cols ≤ 100

Pattern clues in the wording

  • → Minimise the maximum step

These clues point to Dijkstra's Shortest Path: Always expand the closest unfinished node from a min-heap; with non-negative weights, its distance is final.

Stuck? Take one hint at a time

Solution.java · starter
import java.util.*;

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

Write your solution locally or in your editor for now. The in-browser runner (Java first, then Python, C++ and more) will run these tests right here.

Test cases

#InputExpected
1
heights = [[1,2,2],[3,8,2],[5,3,5]]
2
2
heights = [[1,2,3],[3,8,4],[5,3,5]]
1
3
heights = [[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

From slow to fast

Approaches

1. Minimax Dijkstra · O(mn log(mn))
1

Minimax Dijkstra

Time O(mn log(mn)) Space O(mn)

effort[0][0] = 0. Pop the smallest effort; for each neighbour, candidate = max(effort, |Δh|); relax if smaller. Stop when the corner is popped.

Approach 1
import java.util.*;

class Solution {
    public int minimumEffortPath(int[][] heights) {
        int m = heights.length, n = heights[0].length;
        int[][] best = new int[m][n];
        for (int[] row : best) Arrays.fill(row, Integer.MAX_VALUE);
        best[0][0] = 0;
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> Integer.compare(a[0], b[0]));
        pq.offer(new int[]{0, 0, 0});
        int[][] dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
        while (!pq.isEmpty()) {
            int[] t = pq.poll();
            int e = t[0], r = t[1], c = t[2];
            if (r == m - 1 && c == n - 1) return e;
            if (e > best[r][c]) continue;
            for (int[] d : dirs) {
                int nr = r + d[0], nc = c + d[1];
                if (nr < 0 || nc < 0 || nr >= m || nc >= n) continue;
                int ne = Math.max(e, Math.abs(heights[nr][nc] - heights[r][c]));
                if (ne < best[nr][nc]) { best[nr][nc] = ne; pq.offer(new int[]{ne, nr, nc}); }
            }
        }
        return 0;
    }
}

Verdict: The max-combine keeps the greedy argument valid.

Before you submit

Edge cases and common mistakes

Test these inputs

  • 1 × 1 grid (0)
  • Flat grid (0)

Mistakes people make

  • Summing the differences instead of taking the maximum.

Interview

Follow-up questions

Name two other ways to solve it.