Path With Minimum Effort
Given a 2D grid heights of size m x n, find a path from the top-left to the bottom-right that minimises the maximum absolute difference in heights between adjacent cells along the path.
Intuition
This is not a shortest-path problem in the usual sense — you are minimising the maximum edge weight along a path, not the sum. But Dijkstra's algorithm still works: use a min-heap where the priority is the maximum effort seen so far on the path to that cell. Always expand the cell reachable with the smallest bottleneck effort. The first time you reach the bottom-right corner, that effort is the answer — because any other path would have a bottleneck at least as large (Dijkstra's greedy property applies to bottleneck paths too).
The signal is 'minimise the maximum step along any path in a grid'. This is a bottleneck shortest path, and Dijkstra (or binary search + BFS) handles it. Any time a path's cost is defined by its worst edge rather than the sum of edges, the same modified Dijkstra applies — push max(current, edge) instead of current + edge.
Approach
Model the grid as a graph with effort-based edge weights
Each cell is a node. An edge connects adjacent cells (up, down, left, right) with weight abs(heights[r1][c1] - heights[r2][c2]). The path cost is the maximum edge weight along the path, not the sum.
Run modified Dijkstra with a min-heap on bottleneck effort
Push (0, 0, 0) — effort 0, starting at (0, 0). Maintain a dist array where dist[r][c] is the minimum bottleneck effort to reach (r, c). Pop the smallest-effort cell. For each neighbor, compute the effort of using this edge: max(current_effort, abs(heights[r][c] - heights[nr][nc])). If this is less than dist[nr][nc], update and push.
Return the effort when the bottom-right corner is reached
The first time (m-1, n-1) is popped from the heap, the effort is minimal. Time is O(m n log(m n)) for the heap operations. Space is O(m n) for the distance array and heap.
Solution
Common pitfalls
Summing edge weights instead of taking the max
new_effort = effort + abs(heights[r][c] - heights[nr][nc])
new_effort = max(effort, abs(heights[r][c] - heights[nr][nc]))
The problem defines effort as the maximum single step, not the total. Summing gives a different (larger) value that does not answer the question.
Not using a visited/dist check, causing infinite loops
heapq.heappush(heap, (new_effort, nr, nc))
if new_effort < dist[nr][nc]:
dist[nr][nc] = new_effort
heapq.heappush(heap, (new_effort, nr, nc))Without the dist check, the same cell is pushed repeatedly with equal or worse efforts, bloating the heap and slowing the algorithm. In the worst case it may not terminate.
Initialising dist[0][0] to infinity instead of 0
dist = [[float('inf')] * n for _ in range(m)]dist = [[float('inf')] * n for _ in range(m)]
dist[0][0] = 0The starting cell has zero effort. Without setting it, the first pop from the heap has effort 0 but dist[0][0] = inf, and the algorithm may re-process the start or skip valid paths.
Edge cases
Start equals destination. Effort is 0 — no edges to traverse.
Every edge has weight 0. The answer is 0 regardless of the path.
Only one path exists. The answer is the maximum of consecutive differences along that path.