Path With Minimum Effort
Find the route from the top-left to the bottom-right cell whose largest height difference between neighbors is as small as possible, with Dijkstra's algorithm.
Problem Understanding
Path With Minimum Effort: heights is a grid of rows × cols. Moving up, down, left or right, travel from the top-left to the bottom-right. A route's effort is the maximum absolute height difference between two consecutive cells on it. Return the minimum effort.
Examples: [[1,2,2],[3,8,2],[5,3,5]] → 2; [[1,2,3],[3,8,4],[5,3,5]] → 1.
The Intuition: Shortest Path With Max Instead of Plus
Treat the grid as a graph whose edge weights are height differences. It is a shortest-path problem, except a path costs its largest edge rather than the sum:
- Dijkstra expands the cell with the smallest known effort from a heap.
- Relax each neighbor with
max(effort, |Δh|)instead ofeffort + w. - Stop when the target is popped.
The same heap-driven search finds plain shortest paths in Network Delay Time, and the grid-as-graph view is the one from Rotting Oranges.
Interactive Walkthrough
CELL = HEIGHT · BELOW = BEST EFFORT TO REACH IT · TINTED = FINAL
START: EFFORT 0
final
0/9
answer
:
heap (smallest first)
Start at (0, 0) with effort 0; every other cell is ∞. Target: (2, 2)
Next
Pop (0, 0), height 1, effort 0: the smallest on the heap, so it is final
heights
Each cell shows its height, with the best effort found so far beneath it. Final cells are tinted, the move being tried is drawn as an arrow, and the winning path turns green. Try Wall to see a costly direct step avoided.
Dry Run Table
Input: [[1,2,2],[3,8,2],[5,3,5]].
The winning route goes down the left column and along the bottom: heights 1 → 3 → 5 → 3 → 5, steps 2, 2, 2, 2.
| Route | Steps | Effort |
|---|---|---|
| down, down, right, right | 2, 2, 2, 2 | 2 |
| right, right, down, down | 1, 0, 0, 3 | 3 |
| through the 8 | 6+ | 6+ |
Answer: 2.
The Solution Template
Dijkstra with a min-heap. JavaScript and TypeScript include a small binary heap, since the language has none built in.
Path With Minimum Effort Code
1var minimumEffortPath = function(heights) {2 const rows = heights.length, cols = heights[0].length;3 const best = heights.map((row) => row.map(() => Infinity));4 best[0][0] = 0;5 const heap = [[0, 0, 0]];6 const push = (item) => {7 heap.push(item);8 for (let i = heap.length - 1; i > 0 && heap[(i - 1) >> 1][0] > heap[i][0]; i = (i - 1) >> 1) [heap[i], heap[(i - 1) >> 1]] = [heap[(i - 1) >> 1], heap[i]];9 };10 const pop = () => {11 const top = heap[0], last = heap.pop();12 if (heap.length) {13 heap[0] = last;14 for (let i = 0; ; ) {15 let m = i;16 for (const k of [2 * i + 1, 2 * i + 2]) if (k < heap.length && heap[k][0] < heap[m][0]) m = k;17 if (m === i) break;18 [heap[i], heap[m]] = [heap[m], heap[i]];19 i = m;20 }21 }22 return top;23 };24 while (heap.length) {25 const [effort, r, c] = pop();26 if (effort > best[r][c]) continue;27 if (r === rows - 1 && c === cols - 1) return effort;28 for (const [nr, nc] of [[r + 1, c], [r - 1, c], [r, c + 1], [r, c - 1]]) {29 if (nr < 0 || nc < 0 || nr >= rows || nc >= cols) continue;30 const offer = Math.max(effort, Math.abs(heights[nr][nc] - heights[r][c]));31 if (offer < best[nr][nc]) {32 best[nr][nc] = offer;33 push([offer, nr, nc]);34 }35 }36 }37 return 0;38};
Edge Cases & Common Mistakes
- One cell: effort 0.
- Summing steps: the effort is the maximum, not the total.
- Plain BFS: fewest moves is not least effort; you need the heap.
- Stale heap entries: skip them, or the search does extra work and may spread outdated efforts.
- Marking visited on push: a cell can still improve later; finalize it only when popped.
Summary
Run Dijkstra on the grid with max(effort, |Δh|) as the path cost; the effort when the bottom-right cell is popped is the answer. O(R·C log(R·C)) time.
More practice: DSA interview questions with answers · patterns cheat sheet