The problem. You're hiking across a grid of heights, from the top-left cell to the bottom-right, moving up, down, left or right. A route's effort is the largest height difference between two consecutive cells on it. Return the minimum effort needed to cross.
heights = [[1,2,2],[3,8,2],[5,3,5]] -> 2
heights = [[1,2,3],[3,8,4],[5,3,5]] -> 1 (along the top and down the right)
heights = [[1,2,1,1,1],[1,2,1,2,1],[1,2,1,2,1],[1,1,1,2,1]] -> 0 (a perfectly flat winding road)Cells are vertices and neighbouring cells are joined by edges weighted by their height difference. But a route's cost isn't the sum of its edges — it's the largest one. Dijkstra still works, because extending a route can never make its cost go down: the cost of a route through u to v is max(effort to u, |height difference|), which is at least the effort to u.
So run Dijkstra unchanged except for one line: replace d + w with max(e, step). The heap hands back the cell with the easiest route so far; when the bottom-right cell comes out, its effort is the answer.
There's also a second way in. The answer is monotone: if you can cross with effort 5, you can cross with any limit above 5. Questions like that can be binary searched — guess a limit, check it with a plain BFS that only takes steps within the limit, and narrow down.
Binary search the smallest limit for which a BFS, allowed only steps of at most that limit, reaches the bottom-right.
const DIRS = [[-1, 0], [1, 0], [0, -1], [0, 1]]; function minimumEffortPath(heights) { const rows = heights.length, cols = heights[0].length; const canCross = (limit) => { // a plain BFS using only steps of at most limit const seen = heights.map((row) => row.map(() => false)); seen[0][0] = true; const queue = [[0, 0]]; for (let head = 0; head < queue.length; head++) { const [r, c] = queue[head]; if (r === rows - 1 && c === cols - 1) return true; for (const [dr, dc] of DIRS) { const nr = r + dr, nc = c + dc; if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && !seen[nr][nc] && Math.abs(heights[nr][nc] - heights[r][c]) <= limit) { seen[nr][nc] = true; queue.push([nr, nc]); } } } return false; }; let lo = 0, hi = 1000000; // heights are between 1 and 10^6 while (lo < hi) { // the smallest limit that works const mid = Math.floor((lo + hi) / 2); if (canCross(mid)) hi = mid; else lo = mid + 1; } return lo;}Time O(m · n · log H), space O(m · n). H is the range of heights (10⁶ here), so about 20 BFS runs over the m · n cells.
Keep the best effort found for every cell, and a min-heap of [effort, row, col]. Pop the easiest cell, skip it if out of date, stop if it's the target, and otherwise offer each neighbour max(effort, step).
The easiest unsettled cell always comes out of the heap next. Try the map with the peak in the middle.
const DIRS = [[-1, 0], [1, 0], [0, -1], [0, 1]]; function minimumEffortPath(heights) { const rows = heights.length, cols = heights[0].length; const effort = heights.map((row) => row.map(() => Infinity)); // best effort to reach each cell effort[0][0] = 0; const heap = new Heap((a, b) => a[0] - b[0]); // [effort, row, col], easiest first heap.push([0, 0, 0]); while (heap.size() > 0) { const [e, r, c] = heap.pop(); if (e > effort[r][c]) continue; // a stale entry if (r === rows - 1 && c === cols - 1) return e; // settled: no easier path exists for (const [dr, dc] of DIRS) { const nr = r + dr, nc = c + dc; if (nr < 0 || nr >= rows || nc < 0 || nc >= cols) continue; const next = Math.max(e, Math.abs(heights[nr][nc] - heights[r][c])); // a path costs its biggest step if (next < effort[nr][nc]) { effort[nr][nc] = next; heap.push([next, nr, nc]); } } } return 0;}Time O(m · n · log(m · n)), space O(m · n). Each cell has at most 4 edges, so the heap sees O(m · n) pushes and pops at a logarithmic cost each. It stops as soon as the target is settled.
Both are accepted and similarly fast in practice. Dijkstra is the pattern to know; binary search on the answer is a useful second tool whenever "is X enough?" is easy to check and gets easier as X grows.
max(e, height).