#1631 Path With Minimum Effort
frequently reported atGoogle
the problem
In plain words
heights is a rows × cols grid. Walk from the top-left to the bottom-right moving up/down/left/right. A route's effort is its largest absolute height difference between two consecutive cells. Return the minimum effort.
in heights = [[1,2,2],[3,8,2],[5,3,5]]
out 2
1→3→5→3→5 never steps more than 2.
in heights = [[1,2,3],[3,8,4],[5,3,5]]
out 1
in 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]]
out 0
- 1 ≤ rows, cols ≤ 100
- 1 ≤ heights[i][j] ≤ 10⁶
your turn
Try it before you peek
Read the examples, say the brute force out loud, then write code: here or on LeetCode ↗. Stuck for 20 minutes? Open one hint at a time.
Solve it in the browser
LeetCode-style: complete the class. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.
Solutions are hidden so you can try first. Even 20 minutes of real effort makes the answer stick far better than reading it.
Marking the problem solved, or opening every hint, also shows it.
the aha
Key insight
patternDijkstraBinary search on the answerUnion-Find (DSU)
The cost of a path is a max, not a sum — but max is still monotone (extending a path never lowers it). So Dijkstra works with max(effort, step) in place of dist + w.
solutions
From brute force to optimal
"Can I reach the corner with effort ≤ X?" is yes/no and monotone in X. Binary search X; check with BFS that only takes small steps.
- lo = 0, hi = 10⁶.
- mid works (BFS reaches the corner using steps ≤ mid) → hi = mid, else lo = mid + 1.
- Return lo.
≈ 20 binary-search rounds (H = 10⁶), each a full O(mn) BFS.
The visited grid and queue.
class Solution { private static final int[][] DIRS = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}}; public int minimumEffortPath(int[][] heights) { int lo = 0, hi = 1_000_000; // max possible difference while (lo < hi) { int mid = lo + (hi - lo) / 2; if (canReach(heights, mid)) hi = mid; // mid works → try smaller else lo = mid + 1; } return lo; } /** BFS that only uses steps whose height difference is ≤ limit. */ private boolean canReach(int[][] h, int limit) { int rows = h.length, cols = h[0].length; boolean[][] seen = new boolean[rows][cols]; Deque<int[]> queue = new ArrayDeque<>(); queue.offer(new int[] {0, 0}); seen[0][0] = true; while (!queue.isEmpty()) { int[] cur = queue.poll(); if (cur[0] == rows - 1 && cur[1] == cols - 1) return true; for (int[] d : DIRS) { int r = cur[0] + d[0], c = cur[1] + d[1]; if (r < 0 || c < 0 || r >= rows || c >= cols || seen[r][c]) continue; if (Math.abs(h[r][c] - h[cur[0]][cur[1]]) > limit) continue; seen[r][c] = true; queue.offer(new int[] {r, c}); } } return false; }}Sort all neighbour edges by height difference. Add them one by one; the moment both corners are connected, that edge's difference is the answer.
- Build ~2mn edges {diff, a, b}.
- Sort by diff.
- Union each edge; stop when find(start) == find(end).
Sorting the ~2mn edges dominates; the path-halving finds are O(log(mn)) amortized at worst (α with union by rank too).
Edge list and parent array.
class Solution { int[] parent; int find(int x) { while (parent[x] != x) x = parent[x] = parent[parent[x]]; // path halving return x; } public int minimumEffortPath(int[][] heights) { int rows = heights.length, cols = heights[0].length; List<int[]> edges = new ArrayList<>(); // {effort, cellA, cellB} for (int r = 0; r < rows; r++) for (int c = 0; c < cols; c++) { int id = r * cols + c; if (r + 1 < rows) edges.add(new int[] {Math.abs(heights[r][c] - heights[r + 1][c]), id, id + cols}); if (c + 1 < cols) edges.add(new int[] {Math.abs(heights[r][c] - heights[r][c + 1]), id, id + 1}); } edges.sort((a, b) -> Integer.compare(a[0], b[0])); parent = new int[rows * cols]; for (int i = 0; i < parent.length; i++) parent[i] = i; int last = rows * cols - 1; if (last == 0) return 0; // single cell for (int[] e : edges) { parent[find(e[1])] = find(e[2]); // add the cheapest remaining edge if (find(0) == find(last)) return e[0]; // corners just got connected } return 0; }}Dijkstra where a path's cost is the max step so far. Poll the cell with the smallest effort; the corner's first poll is the answer.
- effort[0][0] = 0; heap {0, 0, 0}.
- Poll; if it's the corner, return its effort. Skip stale entries.
- For each neighbour: next = max(e, |Δh|); push if it improves.
≈ 4mn edge relaxations, each with an O(log) heap push.
effort grid and heap.
class Solution { private static final int[][] DIRS = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}}; public int minimumEffortPath(int[][] heights) { int rows = heights.length, cols = heights[0].length; int[][] effort = new int[rows][cols]; // best "max step" to reach each cell for (int[] row : effort) Arrays.fill(row, Integer.MAX_VALUE); effort[0][0] = 0; PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> Integer.compare(a[0], b[0])); pq.offer(new int[] {0, 0, 0}); // {effort, row, col} while (!pq.isEmpty()) { int[] top = pq.poll(); int e = top[0], r = top[1], c = top[2]; if (r == rows - 1 && c == cols - 1) return e; // polled = final if (e > effort[r][c]) continue; for (int[] d : DIRS) { int nr = r + d[0], nc = c + d[1]; if (nr < 0 || nc < 0 || nr >= rows || nc >= cols) continue; // Path cost = the WORST step so far, not the sum. int next = Math.max(e, Math.abs(heights[nr][nc] - heights[r][c])); if (next < effort[nr][nc]) { effort[nr][nc] = next; pq.offer(new int[] {next, nr, nc}); } } } return 0; }}Dry run
in the room
How to say it in the interview
talk track
- Point out the cost is a max, then argue Dijkstra still applies because max never decreases along a path.
- Offer binary search + BFS as an easy-to-trust alternative.
traps
- Summing differences instead of taking the max.
- Returning when the corner is pushed instead of polled.
what they ask next
Follow-ups
Swim in Rising Water (LC 778, below)?
Same minimax idea, but the cost is the max cell value on the path rather than the max step.
before you submit
Edge cases to test
- 1 × 1 grid → 0 (no steps at all).
- A single row or column: the answer is the biggest difference between neighbours.
- All heights equal → 0.
- Heights up to 10⁶: one difference fits in an int — just never sum them.
practise next
Similar problems
- #778Swim in Rising WaterHardin Shortest Paths
- #875Koko Eating BananasMediumin Binary Search
- #1584Min Cost to Connect All PointsMediumin Union-Find & MST