Path With Minimum Effort (LeetCode 1631)

The problem

You get a grid of heights. You start at the top-left cell and want to reach the bottom-right, moving up, down, left or right. The effort of a route is the largest absolute height difference between any two consecutive cells on it. Return the minimum effort over all routes.

Input:
1 2 2
3 8 2
5 3 5

Output: 2

The route 1 → 3 → 5 → 3 → 5 (down the left column, then along the bottom) has steps of 2, 2, 2 and 2, so its effort is 2. Every route through the 8 has a step of at least 5.

How to think about it

Start with brute force. Enumerate every simple path with DFS and track the biggest step on each. The number of paths in a grid is exponential, so this is hopeless beyond tiny inputs.

Model it as a weighted graph. Each cell is a node. Each pair of adjacent cells is joined by an edge whose weight is their height difference. You want the path from corner to corner that minimises the maximum edge weight. This is a minimax or bottleneck path.

The key insight: Dijkstra still works when the path cost is a max. Dijkstra needs one property: extending a path never makes it cheaper. With sums of non-negative weights that holds, and with max(effort_so_far, step) it holds too, since a max never drops. So run Dijkstra with the relaxation ne = max(e, |h[next] - h[cur]|). The min-heap always expands the cell with the lowest effort found so far, and the first time the target is popped, its effort is final.

Which pattern is this? Weighted shortest path with Dijkstra. The tell is “minimise the worst step along a path” on a grid with non-negative costs. (Binary search on the answer plus BFS, or Kruskal with union-find, also work.)

Approach

1. Make an effort grid filled with infinity, set effort[0][0] = 0 and push (0, 0, 0) onto a min-heap.
2. Pop the cell with the smallest effort e. If it is the bottom-right cell, return e.
3. If e is larger than the recorded effort for that cell, it is a stale entry; skip it.
4. For each neighbour, compute ne = max(e, |height difference|). If ne beats the neighbour’s recorded effort, record it and push it.
5. Repeat until the target is popped.

Solution

import heapq
def minimumEffortPath(heights):
    R, C = len(heights), len(heights[0])
    effort = [[float('inf')] * C for _ in range(R)]; effort[0][0] = 0
    h = [(0, 0, 0)]
    while h:
        e, r, c = heapq.heappop(h)
        if (r, c) == (R - 1, C - 1): return e        # first pop of the target is optimal
        if e > effort[r][c]: continue                 # stale heap entry
        for dr, dc in ((1,0),(-1,0),(0,1),(0,-1)):
            nr, nc = r + dr, c + dc
            if 0 <= nr < R and 0 <= nc < C:
                ne = max(e, abs(heights[nr][nc] - heights[r][c]))   # path cost is the max step
                if ne < effort[nr][nc]:
                    effort[nr][nc] = ne; heapq.heappush(h, (ne, nr, nc))
    return 0
# minimumEffortPath([[1,2,2],[3,8,2],[5,3,5]]) -> 2

Dry run

Cells are (row, col). Each row is one pop from the heap:

The answer is 2. The route down the right column pushed the target first, with effort 3, but the heap popped the later effort-2 entry before it.

Complexity

• Time: O(R·C·log(R·C)). Each cell can be pushed a few times (once per improving neighbour), and each heap operation costs a log.
• Space: O(R·C). The effort grid and the heap.

Edge cases and pitfalls

• A 1×1 grid returns 0: the start is the target.
• Returning when you push the target instead of when you pop it can give a non-optimal answer, as the dry run shows (3 was pushed before 2).
• Summing differences solves a different problem. The cost here is the max step.
• Plain BFS fails because edges have different weights.
• Skipping the stale check stays correct but does extra work.

Related problems

• Swim in Rising Water (LeetCode 778): the same minimax Dijkstra, with cell values instead of differences.
• Network Delay Time (LeetCode 743): textbook Dijkstra with summed weights.
• Path with Maximum Probability (LeetCode 1514): Dijkstra with a product and a max-heap.