#1631
Path With Minimum Effort
Medium Dijkstra on a grid (minimax)
- Read
- Understand
- Hints
- Approach
- Solution
- Solved
?The problem
Walk from the top-left to the bottom-right of a height grid. A path's effort is its largest height difference between consecutive cells. Return the minimum effort.
This is a short summary in our own words. Read the full statement and examples on LeetCode: open problem ↗
◎Understanding
Really asking: a path where the biggest single step is as small as possible.
Why this works: Dijkstra where a path's cost is its maximum step, not its sum.
Example: [[1,2,2],[3,8,2],[5,3,5]]
path 1→3→5→3→5 has steps 2, 2, 2, 2 → effort 2✦Hints open one at a time
This is a shortest-path problem where a path's "length" is its maximum step, not its sum.
Dijkstra still works: the new cost is max(current cost, |height difference|).
↗Approach
effort[][] = infinity, start at 0. Min-heap of (effort, r, c). Relax each neighbour with max(e, diff). The first time the target is popped, its effort is final.
</>Solution (Java)
import java.util.*;
class Solution {
public int minimumEffortPath(int[][] heights) {
int m = heights.length, n = heights[0].length;
int[][] effort = new int[m][n];
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, r, c}
pq.offer(new int[]{0, 0, 0});
int[][] dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
while (!pq.isEmpty()) {
int[] cur = pq.poll();
int e = cur[0], r = cur[1], c = cur[2];
if (r == m - 1 && c == n - 1) return e;
if (e > effort[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])); // max, not sum
if (ne < effort[nr][nc]) {
effort[nr][nc] = ne;
pq.offer(new int[]{ne, nr, nc});
}
}
}
return 0;
}
}!Common mistake
Summing the differences like a normal shortest path.
Complexity
- Time: O(m·n log(m·n)).
- Space: O(m·n).
Topic: Graphs
🎬 Episodes 74–85: video coming soon