Path With Minimum Effort
Problem
Given an m × n grid of heights, the effort of a path is the maximum absolute height difference between adjacent cells along it. Return the minimum effort needed to travel from (0,0) to (m-1, n-1).
heights = [[1,2,2],[3,8,2],[5,3,5]]2import heapq
def minimum_effort_path(heights):
m, n = len(heights), len(heights[0])
eff = [[float('inf')] * n for _ in range(m)]
eff[0][0] = 0
h = [(0, 0, 0)]
while h:
e, r, c = heapq.heappop(h)
if (r, c) == (m - 1, n - 1): return e
if e > eff[r][c]: continue
for dr, dc in ((1,0),(-1,0),(0,1),(0,-1)):
nr, nc = r + dr, c + dc
if 0 <= nr < m and 0 <= nc < n:
ne = max(e, abs(heights[nr][nc] - heights[r][c]))
if ne < eff[nr][nc]:
eff[nr][nc] = ne
heapq.heappush(h, (ne, nr, nc))
return 0function minimumEffortPath(h) {
const m = h.length, n = h[0].length;
const eff = Array.from({ length: m }, () => new Array(n).fill(Infinity));
eff[0][0] = 0;
const pq = [[0, 0, 0]];
const dirs = [[1,0],[-1,0],[0,1],[0,-1]];
while (pq.length) {
pq.sort((a, b) => a[0] - b[0]);
const [e, r, c] = pq.shift();
if (r === m - 1 && c === n - 1) return e;
if (e > eff[r][c]) continue;
for (const [dr, dc] of dirs) {
const nr = r + dr, nc = c + dc;
if (nr < 0 || nr >= m || nc < 0 || nc >= n) continue;
const ne = Math.max(e, Math.abs(h[nr][nc] - h[r][c]));
if (ne < eff[nr][nc]) { eff[nr][nc] = ne; pq.push([ne, nr, nc]); }
}
}
return 0;
}class Solution {
public int minimumEffortPath(int[][] h) {
int m = h.length, n = h[0].length;
int[][] eff = new int[m][n];
for (int[] r : eff) Arrays.fill(r, Integer.MAX_VALUE);
eff[0][0] = 0;
PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> 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[] cur = pq.poll();
int e = cur[0], r = cur[1], c = cur[2];
if (r == m - 1 && c == n - 1) return e;
if (e > eff[r][c]) continue;
for (int[] d : dirs) {
int nr = r + d[0], nc = c + d[1];
if (nr < 0 || nr >= m || nc < 0 || nc >= n) continue;
int ne = Math.max(e, Math.abs(h[nr][nc] - h[r][c]));
if (ne < eff[nr][nc]) { eff[nr][nc] = ne; pq.offer(new int[]{ne, nr, nc}); }
}
}
return 0;
}
}int minimumEffortPath(vector<vector<int>>& h) {
int m = h.size(), n = h[0].size();
vector<vector<int>> eff(m, vector<int>(n, INT_MAX));
eff[0][0] = 0;
priority_queue<array<int,3>, vector<array<int,3>>, greater<>> pq;
pq.push({0, 0, 0});
int dirs[4][2] = {{1,0},{-1,0},{0,1},{0,-1}};
while (!pq.empty()) {
auto [e, r, c] = pq.top(); pq.pop();
if (r == m - 1 && c == n - 1) return e;
if (e > eff[r][c]) continue;
for (auto& d : dirs) {
int nr = r + d[0], nc = c + d[1];
if (nr < 0 || nr >= m || nc < 0 || nc >= n) continue;
int ne = max(e, abs(h[nr][nc] - h[r][c]));
if (ne < eff[nr][nc]) { eff[nr][nc] = ne; pq.push({ne, nr, nc}); }
}
}
return 0;
}Explanation
A path's "effort" is its single worst step — the largest height jump between two adjacent cells. We want the path whose worst step is as small as possible, so this is a minimize-the-maximum problem solved with a Dijkstra-style min-heap.
Instead of summing edge weights, each path's cost is max of the steps taken so far. We keep eff[r][c] = the smallest possible "worst step" to reach that cell, start it at 0 for (0,0), and put (0,0,0) into a min-heap.
We always pop the cell with the smallest effort. For each neighbor, the candidate effort is ne = max(e, abs(height diff)). If ne beats the recorded eff[nr][nc], we improve it and push it. The first time we pop the bottom-right corner, that effort is the answer.
The line if e > eff[r][c]: continue throws away stale heap entries so each cell is settled at its best value.
Example: heights = [[1,2,2],[3,8,2],[5,3,5]]. A route like 1 → 2 → 2 → 2 → 5 keeps every step's difference at most 2, and nothing does better, so the answer is 2.