Path With Minimum Effort
Problem statement
You get a grid heights of elevations. You start at the top-left cell and want to reach the bottom-right cell, moving up, down, left or right one cell at a time.
The effort of a route is not its total climb; it is the single largest absolute height difference between two consecutive cells on the route. Return the smallest effort of any route.
Put differently, you are looking for the route whose worst step is as gentle as possible, a bottleneck shortest path.
Examples
Example 1
Input: heights = [[1,3,2],[6,8,3],[5,4,1]]
Output: 2
Explanation: The route 1 → 3 → 2 → 3 → 1 has steps of 2, 1, 1 and 2, so its effort is 2. Every route has to leave the 1 by a step of at least 2.
Example 2
Input: heights = [[4,4,4,4]]
Output: 0
Explanation: Flat ground: every step is 0.
Hints
Approach
Dijkstra on the bottleneck. Let effort[cell] be the smallest route effort known to reach a cell. Pop the cell with the smallest effort from a min-heap. For each neighbour, the effort of going through this cell is max(effort[cell], |step|); if that beats the neighbour's recorded effort, update it and push it.
Dijkstra still works because taking max with a non-negative step never makes a route cheaper, the same property sums have. Return as soon as the bottom-right cell is popped: its effort is final.
O(m · n · log(m · n))Space O(m · n)import heapq def minimum_effort_path(heights): rows, cols = len(heights), len(heights[0]) effort = [[float("inf")] * cols for _ in range(rows)] effort[0][0] = 0 heap = [(0, 0, 0)] while heap: e, r, c = heapq.heappop(heap) if (r, c) == (rows - 1, cols - 1): return e if e > effort[r][c]: continue # stale entry for nr, nc in ((r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)): if 0 <= nr < rows and 0 <= nc < cols: ne = max(e, abs(heights[nr][nc] - heights[r][c])) if ne < effort[nr][nc]: effort[nr][nc] = ne heapq.heappush(heap, (ne, nr, nc)) return 0 print(minimum_effort_path([[1, 3, 2], [6, 8, 3], [5, 4, 1]]))print(minimum_effort_path([[4, 4, 4, 4]]))Follow-up questions
- Return the route itself, not just its effort.
- What if you may also move diagonally? (Only the neighbour list changes.)
Frequently asked questions
Bottleneck paths are common in networks: the usable bandwidth of a route is its narrowest link, and a route is only as reliable as its weakest hop. Recognising that a "minimise the worst step" objective still fits Dijkstra, or fits binary search plus BFS, is the reasoning being tested.
Dijkstra needs extending a route never to make it cheaper. max(e, step) is never less than e, so once a cell is popped with the smallest effort, no later route can improve it. That is the same guarantee non-negative edge weights give for sums.
Yes. Sort all neighbour pairs by height difference and union them in that order; the answer is the difference at which the top-left and bottom-right cells first share a component. It is a nice third approach to mention.