max(4,2)=4. Extending a route cannot reduce this score, which preserves the essential cheapest-frontier reasoning.

A relaxation changes from cost+weight to max(cost,weight). Keep the smallest known effort per cell in a min-heap. Any extension of a waiting route has score at least that route’s current score. Therefore the first valid minimum extraction of a cell is final, just as with additive nonnegative Dijkstra. A smaller effort to the same cell also dominates a larger effort for every identical continuation.

What the function promises: A nonempty rectangular height grid permits four-direction moves. Return the smallest achievable maximum absolute difference between consecutive heights. A one-cell route has effort zero.

from heapq import heappop, heappush

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)]
    while heap:
        effort, r, c = heappop(heap)
        if effort != best[r][c]:
            continue
        if (r, c) == (rows-1, cols-1):
            return effort
        for nr, nc in ((r-1,c), (r+1,c), (r,c-1), (r,c+1)):
            if 0 <= nr < rows and 0 <= nc < cols:
                jump = abs(heights[r][c] - heights[nr][nc])
                candidate = max(effort, jump)
                if candidate < best[nr][nc]:
                    best[nr][nc] = candidate
                    heappush(heap, (candidate, nr, nc))

assert minimum_effort([[1, 5], [2, 6]]) == 4
assert minimum_effort([[1, 2, 2], [3, 8, 2], [5, 3, 5]]) == 2
assert minimum_effort([[9]]) == 0

Work and storage: O(RC log(RC+1)) time and O(RC) auxiliary space on a four-neighbor grid, including lazy heap entries.

When to recognize it: Extending a route changes its score with max, not addition. The score can never decrease as the route grows.

Check before applying it: Fewest steps and smallest total climb are different objectives. Write down how this problem scores a whole path.

Yes. Keep only edges whose height difference is at most the threshold and test reachability. Feasibility is monotone, allowing binary search; sorting edges and joining components is another valid threshold view.