Path With Minimum Effort

Medium

Problem

Move up, down, left or right from the top-left cell to the bottom-right cell of a height grid. A route's effort is its largest absolute height difference between two consecutive cells. Return the minimum possible effort.

Example 1

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

The route 1→3→5→3→5 never steps by more than 2.

Test cases

Case 1

Input:    [[1,2,2],[3,8,2],[5,3,5]]
Expected: 2

Case 2

Input:    [[1,2,3],[3,8,4],[5,3,5]]
Expected: 1

Case 3

Input:    [[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]]
Expected: 0

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
View solutionHide solution1 approach

1. Dijkstra on the maximum step

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

Path cost is its largest height difference, not a sum. Dijkstra still works: always expand the cell with the smallest effort so far. MinHeap is the class from the patterns page.

function minimumEffortPath(h) {
const R = h.length, C = h[0].length;
const dist = Array.from({ length: R }, () => new Array(C).fill(Infinity));
dist[0][0] = 0;
const pq = new MinHeap((a, b) => a[0] - b[0]);
pq.push([0, 0, 0]);
while (pq.size) {
const [d, r, c] = pq.pop();
if (r === R - 1 && c === C - 1) return d;
if (d > dist[r][c]) continue; // stale entry
for (const [dr, dc] of [[1, 0], [-1, 0], [0, 1], [0, -1]]) {
const nr = r + dr, nc = c + dc;
if (nr < 0 || nc < 0 || nr >= R || nc >= C) continue;
const nd = Math.max(d, Math.abs(h[nr][nc] - h[r][c]));
if (nd < dist[nr][nc]) { dist[nr][nc] = nd; pq.push([nd, nr, nc]); }
}
}
return 0;
}

Alternatives: binary search on the effort + BFS, or Union-Find adding edges in increasing weight.