Path with Minimum Effort
You are given a rows x cols grid of heights. You start at the top-left cell and want to reach the bottom-right cell, moving in the four cardinal directions. The effort of a route is the maximum absolute difference in heights between two consecutive cells along it. Return the minimum possible effort needed to make the journey. Run Dijkstra where "distance" is not a running total : relaxing a neighbor takes the larger of the current effort and the new step’s height difference, instead of adding.
Constraints
- rows == heights.length
- cols == heightsi.length
- 1 ≤ rows, cols ≤ 100
- 1 ≤ heightsi[j] ≤ 106
Example
heights = [[1,2,2],[3,8,2],[5,3,5]]2Explanation The route (0,0) → (1,0) → (2,0) → (2,1) → (2,2) has consecutive height differences of 2, 2, 2, 2 — a worst single step of 2, and no route does better.
In plain terms
- Minimax path
- A path chosen to minimize its single worst step, rather than to minimize the sum of every step.
Pop the least-effort cell, relax with max instead of sum
Start at (0,0), effort 0. Every other cell is unknown.
What happens in this step
effort[0,0] = 0 every other cell = ∞ Only the top-left starting cell has a known effort (0, standing still). Every other cell is unreached.
Steps to visualize
- Set the effort of the top-left cell to 0 and every other cell to infinity.
- Repeatedly pop the unfinalized cell with the smallest effort.
- Relax each neighbor: its candidate effort is the larger of the current cell’s effort and the height difference between them.
- Once the bottom-right cell is popped, its effort is the answer.
Walk through the code
Same walkthrough, now with the code. Press Next to move one step and watch which lines run.
Start at (0,0), effort 0. Every other cell is unknown.
What happens in this step
effort[0,0] = 0 every other cell = ∞ Only the top-left starting cell has a known effort (0, standing still). Every other cell is unreached.
Solution
function minimumEffortPath(heights) {
const rows = heights.length;
const cols = heights[0].length;
const effort = Array.from({ length: rows }, () => new Array(cols).fill(Infinity));
effort[0][0] = 0;
const visited = Array.from({ length: rows }, () => new Array(cols).fill(false));
const directions = [
[1, 0],
[-1, 0],
[0, 1],
[0, -1],
];
while (true) {
let cr = -1;
let cc = -1;
let best = Infinity;
for (let r = 0; r < rows; r++) {
for (let c = 0; c < cols; c++) {
if (!visited[r][c] && effort[r][c] < best) {
best = effort[r][c];
cr = r;
cc = c;
}
}
}
if (cr === -1) break;
if (cr === rows - 1 && cc === cols - 1) break; // destination popped, done
visited[cr][cc] = true;
for (const [dr, dc] of directions) {
const nr = cr + dr;
const nc = cc + dc;
if (nr < 0 || nr >= rows || nc < 0 || nc >= cols || visited[nr][nc]) continue;
const diff = Math.abs(heights[nr][nc] - heights[cr][cc]);
const candidate = Math.max(effort[cr][cc], diff); // max, not sum
if (candidate < effort[nr][nc]) {
effort[nr][nc] = candidate;
}
}
}
return effort[rows - 1][cols - 1];
}- Time
- O((rows * cols)^2)
- Space
- O(rows * cols)
Test cases
| Input | Expected | Covers |
|---|---|---|
heights = [[1,2,2],[3,8,2],[5,3,5]] | 2 | example from the docstring |
heights = [[1,2,3],[3,8,4],[5,3,5]] | 1 | a gentler route exists with worst step just 1 |
heights = [[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]] | 0 | an entirely flat route exists, needing zero effort |
heights = [[5]] | 0 | start and destination are the same single cell |
heights = [[1,10]] | 9 | only one possible route, a straight line |
heights = [[1],[10]] | 9 | only one possible route, moving straight down |
heights = [[1,2],[2,3]] | 1 | both routes through a 2x2 grid tie at the same worst step |