Path With Minimum Effort
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
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.