DSA Swim in Rising Water

The problem

A square grid holds one height per cell. A swimmer starts at the top-left cell and must reach the bottom-right cell, moving one step up, down, left, or right at a time.

The cost of a path is the highest cell standing on it, including both ends. The answer is the smallest cost over all paths. That cost is the water level the swimmer must wait for.

cases = [
    ([[0, 2], [1, 3]], 3),
    ([[0, 1, 2, 3, 4], [24, 23, 22, 21, 5], [12, 13, 14, 15, 16],
      [11, 17, 18, 19, 20], [10, 9, 8, 7, 6]], 16),
    ([[0]], 0),
    ([[5, 1], [1, 1]], 5),
]
for grid, expected in cases:
    print("grid rows:", len(grid), "smallest level:", expected)

The last case makes the start cell the bottleneck. No path can cost less than 5 there, because every path stands on the start. The big spiral case answers 16, far below its largest height of 24.

Intuition: fewest steps is the wrong target

The first idea counts steps and looks for a short path. Step count ignores heights entirely. Two paths with the same length can carry very different highest cells.

The grid below separates the two measures cleanly. Its top route and its bottom route both take four steps. One route wades over cells of height 8, and the other never rises above 1.

grid = [[0, 8, 8], [1, 8, 1], [1, 1, 1]]
top = [(0, 0), (0, 1), (0, 2), (1, 2), (2, 2)]
bottom = [(0, 0), (1, 0), (2, 0), (2, 1), (2, 2)]
for name, path in [("top", top), ("bottom", bottom)]:
    heights = [grid[r][c] for r, c in path]
    print(name, "path heights:", heights, "steps:", len(path) - 1, "cost:", max(heights))

A step-counting search can return either path and call both equal. The problem only cares about the highest cell. The search key has to be that highest cell, not the step count.

Brute force: walk every simple path

A simple path never revisits a cell. The brute force walks every simple path from the start to the target. It keeps the smallest highest-cell cost it ever sees.

A visited set enforces the simple rule inside the walk. The path count is recorded, because that count is the brute force's bill.

def brute(grid):
    n = len(grid)
    best = [10 ** 9]
    paths = [0]
    def dfs(r, c, seen, top):
        if (r, c) == (n - 1, n - 1):
            paths[0] += 1
            best[0] = min(best[0], top)
            return
        for nr, nc in [(r - 1, c), (r, c + 1), (r + 1, c), (r, c - 1)]:
            if 0 <= nr < n and 0 <= nc < n and (nr, nc) not in seen:
                seen.add((nr, nc))
                dfs(nr, nc, seen, max(top, grid[nr][nc]))
                seen.remove((nr, nc))
    dfs(0, 0, {(0, 0)}, grid[0][0])
    return best[0], paths[0]

print("small grid:", brute([[0, 2], [1, 3]]))
print("trap grid:", brute([[0, 8, 8], [1, 8, 1], [1, 1, 1]]))

Both answers are correct, and the trap grid already needs twelve full paths. Detours multiply the count fast, because a simple path may wander anywhere before finishing. The optimal method never walks a path at all.

The optimal solution: Dijkstra where the price is the highest cell

Each cell carries the lowest possible highest-cell cost of any path reaching it, and a heap always settles the unsettled cell with the smallest such cost next. That pricing rule is the whole method.

Stepping into a neighbour prices the step at the larger of the current cost and the neighbour's height. The first time the target leaves the heap, its price is final. Any other route would have to pass through a cell already priced at least as high.

import heapq

def swim(grid):
    n = len(grid)
    best = [[10 ** 9] * n for _ in range(n)]
    best[0][0] = grid[0][0]
    heap = [(grid[0][0], 0, 0)]
    pops = 0
    while heap:
        cost, r, c = heapq.heappop(heap)
        pops += 1
        if cost > best[r][c]:
            continue
        if (r, c) == (n - 1, n - 1):
            break
        for nr, nc in [(r - 1, c), (r, c + 1), (r + 1, c), (r, c - 1)]:
            if 0 <= nr < n and 0 <= nc < n:
                new = max(cost, grid[nr][nc])
                if new < best[nr][nc]:
                    best[nr][nc] = new
                    heapq.heappush(heap, (new, nr, nc))
    return best[n - 1][n - 1], pops

cases = [
    [[0, 2], [1, 3]],
    [[0, 1, 2, 3, 4], [24, 23, 22, 21, 5], [12, 13, 14, 15, 16],
     [11, 17, 18, 19, 20], [10, 9, 8, 7, 6]],
    [[0]],
    [[5, 1], [1, 1]],
]
for grid in cases:
    answer, pops = swim(grid)
    print("grid rows:", len(grid), "answer:", answer, "heap pops:", pops)

All four answers match the cases from the first section. The spiral grid settles at 16, although it holds cells up to 24. The heap pops stay close to the cell count, as the complexity section shows.

Walkthrough: settling the small grid

The walk runs the heap method on the grid [[0, 2], [1, 3]]. Each printed step settles one cell for good. The best table after each step shows the lowest known cost per cell.

import heapq

grid = [[0, 2], [1, 3]]
n = 2
best = [[10 ** 9] * n for _ in range(n)]
best[0][0] = grid[0][0]
heap = [(grid[0][0], 0, 0)]

def show():
    return [[best[r][c] if best[r][c] < 10 ** 9 else "-"
             for c in range(n)] for r in range(n)]

while heap:
    cost, r, c = heapq.heappop(heap)
    if cost > best[r][c]:
        continue
    print("settle cell", (r, c), "at cost", cost, "best table:", show())
    if (r, c) == (n - 1, n - 1):
        break
    for nr, nc in [(r - 1, c), (r, c + 1), (r + 1, c), (r, c - 1)]:
        if 0 <= nr < n and 0 <= nc < n:
            new = max(cost, grid[nr][nc])
            if new < best[nr][nc]:
                best[nr][nc] = new
                heapq.heappush(heap, (new, nr, nc))
print("answer:", best[n - 1][n - 1])

The start settles at 0, and its neighbours price at 2 and 1. The cell priced 1 settles next, although it is not the target. Its expansion prices the target at 3, and the target settles last at that price. A dash in the table marks a cell not yet priced.

Complexity

The heap method settles each cell once and pushes each edge a small number of times, so its time is O(n^2 log n) on an n by n grid. The best table holds one entry per cell, so its space is O(n^2).

The brute force pays per path, and path counts grow explosively. The counts below come from walking grids of plain zeros, where only the counting matters.

def count_paths(n):
    paths = [0]
    def dfs(r, c, seen):
        if (r, c) == (n - 1, n - 1):
            paths[0] += 1
            return
        for nr, nc in [(r - 1, c), (r, c + 1), (r + 1, c), (r, c - 1)]:
            if 0 <= nr < n and 0 <= nc < n and (nr, nc) not in seen:
                seen.add((nr, nc))
                dfs(nr, nc, seen)
                seen.remove((nr, nc))
    dfs(0, 0, {(0, 0)})
    return paths[0]

for n in [2, 3, 4]:
    print("grid", n, "x", n, "- simple paths:", count_paths(n),
          " cells the heap settles:", n * n)

A 4 by 4 grid already holds 184 simple paths against 16 cells. Larger grids widen the gap beyond rescue. The heap method's bill follows the cells, not the paths.

Edge cases and pitfalls

A one-cell grid answers its only height. The start and the target are the same cell, so no step is ever taken. Code that assumes at least one move mishandles this case.

Forgetting the starting cell in the maximum is the classic bug. A path's cost includes both ends. The predicate view below shows the same truth from the other side: a level below the start height can never work.

import heapq

def swim(grid):
    n = len(grid)
    best = [[10 ** 9] * n for _ in range(n)]
    best[0][0] = grid[0][0]
    heap = [(grid[0][0], 0, 0)]
    pops = 0
    while heap:
        cost, r, c = heapq.heappop(heap)
        pops += 1
        if cost > best[r][c]:
            continue
        if (r, c) == (n - 1, n - 1):
            break
        for nr, nc in [(r - 1, c), (r, c + 1), (r + 1, c), (r, c - 1)]:
            if 0 <= nr < n and 0 <= nc < n:
                new = max(cost, grid[nr][nc])
                if new < best[nr][nc]:
                    best[nr][nc] = new
                    heapq.heappush(heap, (new, nr, nc))
    return best[n - 1][n - 1], pops

from collections import deque

def reachable(grid, level):
    n = len(grid)
    if grid[0][0] > level:
        return False
    seen = {(0, 0)}
    dq = deque([(0, 0)])
    while dq:
        r, c = dq.popleft()
        if (r, c) == (n - 1, n - 1):
            return True
        for nr, nc in [(r - 1, c), (r, c + 1), (r + 1, c), (r, c - 1)]:
            if 0 <= nr < n and 0 <= nc < n and (nr, nc) not in seen:
                if grid[nr][nc] <= level:
                    seen.add((nr, nc))
                    dq.append((nr, nc))
    return False

print("one cell:", swim([[7]]))
print("start is the bottleneck:", swim([[5, 1], [1, 1]]))
grid = [[5, 1], [1, 1]]
for level in [4, 5]:
    print("level", level, "reachable:", reachable(grid, level))
print("all heights equal:", swim([[3, 3], [3, 3]]))

Level 4 fails on the bottleneck grid before any step, because the start itself stands at 5. Level 5 succeeds. That threshold behaviour also licenses a binary search on the level, an alternative route to the same answer.