DSA Path with Minimum Effort

The problem

Path with Minimum Effort asks for a route across a grid of heights. A route moves up, down, left or right between neighbouring cells. It starts at the top-left cell and ends at the bottom-right cell.

A height gap is the absolute difference between two neighbouring cells. The effort of a route is its single largest gap. The answer is the smallest effort over all routes.

cases = [
    ([[1, 2, 2], [3, 8, 2], [5, 3, 5]], 2),
    ([[1, 2, 1, 1], [2, 9, 9, 1], [1, 1, 1, 1]], 1),
    ([[1, 10], [2, 3]], 1),
    ([[7]], 0),
]
for grid, expected in cases:
    print("grid:", grid, "expected effort:", expected)

Read the third grid by hand. Down then right crosses gaps of 1 and 1. Right then down crosses gaps of 9 and 7. The route with the smaller worst gap wins.

Intuition: price a route by its worst gap, not its total

The first idea prices a route by adding its gaps. That price feels natural, because adding costs is how many route problems work. It is the wrong price for this problem.

route_a = [1, 6, 3]
route_b = [4, 4, 4]
print("route A gaps:", route_a, "total:", sum(route_a), "worst gap:", max(route_a))
print("route B gaps:", route_b, "total:", sum(route_b), "worst gap:", max(route_b))
print("smaller total: A")
print("smaller effort: B")

Route A has the smaller total. Route B has the smaller worst gap. Effort cares only about the worst gap, so route B wins. One hard climb sets the price of a whole route.

Brute force: walk every route

The brute force walks every route that never revisits a cell. It tracks the worst gap on the current route. At the far corner it keeps the smallest worst gap seen so far.

grid = [[1, 2, 2], [3, 8, 2], [5, 3, 5]]
rows = len(grid)
cols = len(grid[0])
routes = 0
best = None

def walk(r, c, visited, worst):
    global routes, best
    if r == rows - 1 and c == cols - 1:
        routes += 1
        if best is None or worst < best:
            best = worst
        return
    for dr, dc in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
        nr, nc = r + dr, c + dc
        if 0 <= nr < rows and 0 <= nc < cols and (nr, nc) not in visited:
            visited.add((nr, nc))
            walk(nr, nc, visited, max(worst, abs(grid[nr][nc] - grid[r][c])))
            visited.remove((nr, nc))

walk(0, 0, {(0, 0)}, 0)
print("routes explored:", routes)
print("best effort:", best)

Twelve routes cross this small grid, and the walk explores every one in full. It cannot stop a route early, because a later stretch might still matter for the count. A larger grid multiplies the route count, as the complexity section shows.

The optimal solution: settle cells in rising effort order

The state is the best effort known for each cell, and the candidate effort for a neighbour is the larger of the effort so far and the new gap. That one sentence is the whole method.

A heap holds cells by candidate effort. The smallest candidate leaves the heap first, and that cell is settled. No later route can reach a settled cell with a smaller worst gap. Relaxing a neighbour means offering it a candidate and keeping the smaller stored effort.

import heapq

def min_effort(heights):
    rows = len(heights)
    cols = len(heights[0])
    best = [[None] * cols for _ in range(rows)]
    best[0][0] = 0
    heap = [(0, 0, 0)]
    while heap:
        effort, r, c = heapq.heappop(heap)
        if best[r][c] is not None and effort > best[r][c]:
            continue
        if r == rows - 1 and c == cols - 1:
            return effort
        for dr, dc in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
            nr, nc = r + dr, c + dc
            if 0 <= nr < rows and 0 <= nc < cols:
                gap = abs(heights[nr][nc] - heights[r][c])
                cand = max(effort, gap)
                if best[nr][nc] is None or cand < best[nr][nc]:
                    best[nr][nc] = cand
                    heapq.heappush(heap, (cand, nr, nc))
    return best[rows - 1][cols - 1]

cases = [
    ([[1, 2, 2], [3, 8, 2], [5, 3, 5]], 2),
    ([[1, 2, 1, 1], [2, 9, 9, 1], [1, 1, 1, 1]], 1),
    ([[1, 10], [2, 3]], 1),
    ([[7]], 0),
]
for grid, expected in cases:
    result = min_effort(grid)
    print("expected:", expected, "got:", result, "match:", result == expected)

All four cases match. The single cell answers 0, because a route with no steps has no gap. The tall centre cell of the first grid is routed around, never settled early with a large effort.

Walkthrough: settling the first grid

The walk uses the first grid. The heap settles one cell at a time. Each pair of lines prints the settled cell and the best table as it stands at that moment.

import heapq

grid = [[1, 2, 2], [3, 8, 2], [5, 3, 5]]
rows = len(grid)
cols = len(grid[0])
best = [[None] * cols for _ in range(rows)]
best[0][0] = 0
heap = [(0, 0, 0)]
while heap:
    effort, r, c = heapq.heappop(heap)
    if best[r][c] is not None and effort > best[r][c]:
        continue
    print("settled", (r, c), "effort", effort)
    print("best:", best)
    if r == rows - 1 and c == cols - 1:
        break
    for dr, dc in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
        nr, nc = r + dr, c + dc
        if 0 <= nr < rows and 0 <= nc < cols:
            cand = max(effort, abs(grid[nr][nc] - grid[r][c]))
            if best[nr][nc] is None or cand < best[nr][nc]:
                best[nr][nc] = cand
                heapq.heappush(heap, (cand, nr, nc))

The target settles last with effort 2. One route that earns it runs down, down, right, right. Its gaps are 2, 2, 2 and 2. The answer is read straight off the settled target.

Complexity

Time is O(cells log cells), where cells is rows times columns. Each cell settles once, each settle checks four neighbours, and each heap operation costs a log factor.

Space is O(cells). The best table holds one entry per cell, and the heap holds at most one entry per cell.

def count_routes(n):
    routes = 0
    def walk(r, c, visited):
        nonlocal routes
        if r == n - 1 and c == n - 1:
            routes += 1
            return
        for dr, dc in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
            nr, nc = r + dr, c + dc
            if 0 <= nr < n and 0 <= nc < n and (nr, nc) not in visited:
                visited.add((nr, nc))
                walk(nr, nc, visited)
                visited.remove((nr, nc))
    walk(0, 0, {(0, 0)})
    return routes

import heapq

def count_relaxations(n):
    grid = [[1] * n for _ in range(n)]
    best = [[None] * n for _ in range(n)]
    best[0][0] = 0
    heap = [(0, 0, 0)]
    checks = 0
    while heap:
        effort, r, c = heapq.heappop(heap)
        if best[r][c] is not None and effort > best[r][c]:
            continue
        if r == n - 1 and c == n - 1:
            break
        for dr, dc in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
            nr, nc = r + dr, c + dc
            if 0 <= nr < n and 0 <= nc < n:
                checks += 1
                cand = max(effort, abs(grid[nr][nc] - grid[r][c]))
                if best[nr][nc] is None or cand < best[nr][nc]:
                    best[nr][nc] = cand
                    heapq.heappush(heap, (cand, nr, nc))
    return checks

for n in [2, 3, 4]:
    print("grid", n, "x", n, "- routes:", count_routes(n), " relaxation checks:", count_relaxations(n))

The route count jumps from 2 to 12 to 184. The relaxation checks stay close to the edge count of the grid. The heap method pays per edge, not per route.

Edge cases and pitfalls

A one-cell grid needs no step at all. A flat grid needs no climb. A single row or column allows exactly one route, and its worst gap is the answer.

import heapq

def min_effort(heights):
    rows = len(heights)
    cols = len(heights[0])
    best = [[None] * cols for _ in range(rows)]
    best[0][0] = 0
    heap = [(0, 0, 0)]
    while heap:
        effort, r, c = heapq.heappop(heap)
        if best[r][c] is not None and effort > best[r][c]:
            continue
        if r == rows - 1 and c == cols - 1:
            return effort
        for dr, dc in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
            nr, nc = r + dr, c + dc
            if 0 <= nr < rows and 0 <= nc < cols:
                cand = max(effort, abs(heights[nr][nc] - heights[r][c]))
                if best[nr][nc] is None or cand < best[nr][nc]:
                    best[nr][nc] = cand
                    heapq.heappush(heap, (cand, nr, nc))
    return best[rows - 1][cols - 1]

print("one cell:", min_effort([[7]]))
print("flat grid:", min_effort([[3, 3], [3, 3]]))
print("one row:", min_effort([[1, 5, 2]]))
print("one column:", min_effort([[1], [4], [2]]))

The classic mistake adds the gaps along a route instead of taking the largest one. The winning route of the walkthrough shows the size of that error.

gaps = [2, 2, 2, 2]
print("added price:", sum(gaps))
print("true effort:", max(gaps))

Every grid is fully connected by its four moves, so an unreachable target cannot occur. A wall of tall cells still has a route. Its effort is simply large.