The path with the least effort
A grid gives the height of each cell. You start at the top-left cell and must reach the bottom-right cell, moving up, down, left or right. The effort of a route is the largest absolute difference in height between two consecutive cells on it. Return the minimum effort over all routes.
Examples
| Input | Output | Why |
|---|---|---|
heights = [[1,2,2],[3,8,2],[5,3,5]] | 2 | Down the left side and along the bottom: every step changes height by at most 2. |
heights = [[1,2,3],[3,8,4],[5,3,5]] | 1 | Along the top and down the right side, one unit at a time. |
heights = [[7]] | 0 | Already there. |
Constraints
- 1 ≤ rows, cols ≤ 100
- 1 ≤ heights[r][c] ≤ 10⁶
Hints
Hint 1
A route's cost is not a sum, it is the maximum step along it. Extending a route can only keep that maximum or raise it.
Hint 2
That property is all Dijkstra needs. Keep the best effort found for each cell and always settle the cell with the smallest.
Hint 3
When you move from a cell with effort e into a neighbour, the neighbour's candidate effort is max(e, |height difference|).
Where people lose marks
- Summing the differences, which answers a different question.
- Plain breadth-first search, which minimises the number of steps, not the effort.
- Stopping when the target is first pushed rather than when it is popped.
Dry run on [[1,2,2],[3,8,2],[5,3,5]]
Read it one frame at a time, the way you would trace the code on paper in an interview. Each frame shows the state after the step it describes.
-
Step 1 / 8settled cells and their effort(0,0):00
Settle (0, 0) at effort 0: nothing left in the heap is lower. Neighbours updated: (1,0)→2, (0,1)→1.
-
Step 2 / 8settled cells and their effort(0,0):00(0,1):11
Settle (0, 1) at effort 1: nothing left in the heap is lower. Neighbours updated: (1,1)→6, (0,2)→1.
-
Step 3 / 8settled cells and their effort(0,0):00(0,1):11(0,2):12
Settle (0, 2) at effort 1: nothing left in the heap is lower. Neighbours updated: (1,2)→1.
-
Step 4 / 8settled cells and their effort(0,0):00(0,1):11(0,2):12(1,2):13
Settle (1, 2) at effort 1: nothing left in the heap is lower. Neighbours updated: (2,2)→3.
-
Step 5 / 8settled cells and their effort(0,0):00(0,1):11(0,2):12(1,2):13(1,0):24
Settle (1, 0) at effort 2: nothing left in the heap is lower. Neighbours updated: (2,0)→2, (1,1)→5.
-
Step 6 / 8settled cells and their effort(0,0):00(0,1):11(0,2):12(1,2):13(1,0):24(2,0):25
Settle (2, 0) at effort 2: nothing left in the heap is lower. Neighbours updated: (2,1)→2.
-
Step 7 / 8settled cells and their effort(0,0):00(0,1):11(0,2):12(1,2):13(1,0):24(2,0):25(2,1):26
Settle (2, 1) at effort 2: nothing left in the heap is lower. Neighbours updated: (2,2)→2.
-
Step 8 / 8settled cells and their effort(0,0):00(0,1):11(0,2):12(1,2):13(1,0):24(2,0):25(2,1):26(2,2):27
Settle (2, 2) at effort 2: nothing left in the heap is lower. It is the target: the answer is 2.
How to think about it
The effort of a route is the maximum of its steps, and extending a route never lowers that maximum. So the
cell with the smallest effort among those not yet settled is final, by the same argument as for ordinary distances.
Run Dijkstra on the grid with one change: relaxing an edge computes max(effort[u], |h[u] − h[v]|)
instead of a sum.
An alternative, equally valid, is to binary-search the answer: for a limit L, a search that only takes steps of at most L decides whether the corner is reachable, and the smallest L that works is the answer.
Complexity. Time O(rows · cols · log(rows · cols)) · Space O(rows · cols)
The solution, in six languages
Each one is compiled and run against the test table before it is published. Java is reviewed by hand.
import heapq
def minimum_effort(heights):
rows, cols = len(heights), len(heights[0])
best = [[float('inf')] * cols for _ in range(rows)]
best[0][0] = 0
heap = [(0, 0, 0)] # (effort, row, col)
while heap:
e, r, c = heapq.heappop(heap)
if e > best[r][c]:
continue # stale entry
if r == rows - 1 and c == cols - 1:
return e
for a, b in ((r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)):
if 0 <= a < rows and 0 <= b < cols:
ne = max(e, abs(heights[a][b] - heights[r][c])) # max, not +
if ne < best[a][b]:
best[a][b] = ne
heapq.heappush(heap, (ne, a, b))
return 0#include <array>
#include <climits>
#include <cstdlib>
#include <functional>
#include <queue>
#include <vector>
int solve(const std::vector<std::vector<int>>& heights) {
const int rows = heights.size(), cols = heights[0].size();
std::vector<std::vector<int>> best(rows, std::vector<int>(cols, INT_MAX));
best[0][0] = 0;
using Entry = std::array<int, 3>; // effort, row, col
std::priority_queue<Entry, std::vector<Entry>, std::greater<Entry>> heap;
heap.push({0, 0, 0});
const int dr[] = {1, -1, 0, 0}, dc[] = {0, 0, 1, -1};
while (!heap.empty()) {
auto [e, r, c] = heap.top();
heap.pop();
if (e > best[r][c]) continue; // stale entry
if (r == rows - 1 && c == cols - 1) return e;
for (int d = 0; d < 4; ++d) {
int a = r + dr[d], b = c + dc[d];
if (a < 0 || b < 0 || a >= rows || b >= cols) continue;
int ne = std::max(e, std::abs(heights[a][b] - heights[r][c])); // max, not +
if (ne < best[a][b]) { best[a][b] = ne; heap.push({ne, a, b}); }
}
}
return 0;
}import java.util.*;
class Solution {
public int minimumEffort(int[][] heights) {
int rows = heights.length, cols = heights[0].length;
int[][] best = new int[rows][cols];
for (int[] row : best) Arrays.fill(row, Integer.MAX_VALUE);
best[0][0] = 0;
PriorityQueue<int[]> heap = new PriorityQueue<>((x, y) -> Integer.compare(x[0], y[0]));
heap.add(new int[]{0, 0, 0}); // effort, row, col
int[] dr = {1, -1, 0, 0}, dc = {0, 0, 1, -1};
while (!heap.isEmpty()) {
int[] t = heap.poll();
int e = t[0], r = t[1], c = t[2];
if (e > best[r][c]) continue; // stale entry
if (r == rows - 1 && c == cols - 1) return e;
for (int d = 0; d < 4; d++) {
int a = r + dr[d], b = c + dc[d];
if (a < 0 || b < 0 || a >= rows || b >= cols) continue;
int ne = Math.max(e, Math.abs(heights[a][b] - heights[r][c])); // max, not +
if (ne < best[a][b]) { best[a][b] = ne; heap.add(new int[]{ne, a, b}); }
}
}
return 0;
}
}function minimumEffort(heights) {
const rows = heights.length, cols = heights[0].length;
const best = Array.from({ length: rows }, () => new Array(cols).fill(Infinity));
best[0][0] = 0;
// binary min-heap of [effort, row, col]
const heap = [[0, 0, 0]];
const push = e => { heap.push(e); let i = heap.length - 1; while (i > 0) { const p = (i - 1) >> 1; if (heap[p][0] <= heap[i][0]) break; [heap[p], heap[i]] = [heap[i], heap[p]]; i = p; } };
const pop = () => { const top = heap[0], last = heap.pop(); if (heap.length) { heap[0] = last; let i = 0; for (;;) { const l = 2 * i + 1, r = l + 1; let m = i; if (l < heap.length && heap[l][0] < heap[m][0]) m = l; if (r < heap.length && heap[r][0] < heap[m][0]) m = r; if (m === i) break; [heap[m], heap[i]] = [heap[i], heap[m]]; i = m; } } return top; };
while (heap.length) {
const [e, r, c] = pop();
if (e > best[r][c]) continue; // stale entry
if (r === rows - 1 && c === cols - 1) return e;
for (const [a, b] of [[r + 1, c], [r - 1, c], [r, c + 1], [r, c - 1]]) {
if (a < 0 || b < 0 || a >= rows || b >= cols) continue;
const ne = Math.max(e, Math.abs(heights[a][b] - heights[r][c])); // max, not +
if (ne < best[a][b]) { best[a][b] = ne; push([ne, a, b]); }
}
}
return 0;
}use std::cmp::Reverse;
use std::collections::BinaryHeap;
fn solve<const C: usize>(heights: &[[i64; C]]) -> i64 {
let rows = heights.len();
let mut best = vec![[i64::MAX; C]; rows];
best[0][0] = 0;
let mut heap = BinaryHeap::from([Reverse((0i64, 0usize, 0usize))]); // effort, row, col
while let Some(Reverse((e, r, c))) = heap.pop() {
if e > best[r][c] {
continue; // stale entry
}
if r == rows - 1 && c == C - 1 {
return e;
}
let around = [(r + 1, c), (r.wrapping_sub(1), c), (r, c + 1), (r, c.wrapping_sub(1))];
for (a, b) in around {
if a >= rows || b >= C {
continue;
}
let ne = e.max((heights[a][b] - heights[r][c]).abs()); // max, not +
if ne < best[a][b] {
best[a][b] = ne;
heap.push(Reverse((ne, a, b)));
}
}
}
0
}import qualified Data.Map.Strict as M
import qualified Data.Set as S
solve :: [[Int]] -> Int
solve heights = go (S.singleton (0, (0, 0))) (M.singleton (0, 0) 0)
where
rows = length heights
cols = length (head heights)
h = M.fromList [((r, c), x) | (r, row) <- zip [0 ..] heights, (c, x) <- zip [0 ..] row]
-- the set of (effort, cell) is the heap; the map holds the best effort found per cell
go heap best = case S.minView heap of
Nothing -> 0
Just ((e, p@(r, c)), rest)
| e > M.findWithDefault maxBound p best -> go rest best -- stale entry
| r == rows - 1 && c == cols - 1 -> e
| otherwise ->
let moves = [ (ne, q) | q <- [(r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)], M.member q h
, let ne = max e (abs (h M.! q - h M.! p)) -- max, not +
, ne < M.findWithDefault maxBound q best ]
in go (foldr S.insert rest moves) (foldr (\(ne, q) -> M.insert q ne) best moves)Variants to try
- Return the route itself.
- Diagonal moves are allowed as well: eight neighbours, same algorithm.
- Minimise the number of steps among the routes of minimum effort: compare pairs (effort, steps).
Next problems
Swim in rising water
Water rises one unit per second and a cell can be entered once it is covered. Find the earliest time the far corner can be reached.
Open the problem → Easy12 minCount the islands in a grid
Every unvisited land cell starts a new island; flood it so it is never counted again. The first graph problem most interviews ask.
Open the problem → Easy12 minDoes an undirected graph contain a cycle?
Return true if the graph has a cycle: a search that meets a visited node by any edge but the one it came along has found one.
Open the problem →Write a solution and run it against the real test table.
Keep going
Swim in rising water
Water rises one unit per second and a cell can be entered once it is covered. Find the earliest time the far corner can be reached.
Open the problem → Easy12 minCount the islands in a grid
Every unvisited land cell starts a new island; flood it so it is never counted again. The first graph problem most interviews ask.
Open the problem → Easy12 minDoes an undirected graph contain a cycle?
Return true if the graph has a cycle: a search that meets a visited node by any edge but the one it came along has found one.
Open the problem → GraphsThe pattern behind it
Grids, networks and dependencies are all graphs. Breadth-first search finds shortest paths, depth-first search and union-find find what is connected, Dijkstra handles weighted edges, and a queue of nodes with no remaining prerequisites gives an order.
Read the pattern →Preparing for a real process? Quant interview preparation, or book a free 20-minute call.