LeetCode 778 · Advanced Graphs

Swim in Rising Water, explained with a picture

Waiting for the flood to let you swim across.

HardAdvanced Graphs
▶ Watch it step by step

The problem

A grid of ground heights floods: at time t, the water level is t. You can swim between neighbouring squares if both are ≤ t. Find the earliest time you can swim from the top-left to the bottom-right.

Input:  the 5 × 5 heights shown
Output: 16

Picture it

Picture a valley slowly flooding. Your route is only as good as its highest square, since you must wait until the water covers it. We always explore next the reachable square needing the lowest water (a min-heap). The highest square we were forced to step on by the time we reach the corner is the answer.

How to recognise it

  • A grid where each cell has a height or threshold, and you move between neighbours.
  • The cost of a route is the largest value on it, not the sum of its values.
  • You want the route whose worst moment is as small as possible, with free choice of direction at every step.
  • With n up to 50 the grid has 2,500 cells, so repeating a full search per possible time is fine, but you can do much better.

Start with brute force

Try each water level t = 0, 1, 2, … in turn. For each t, run a BFS from the top-left that may enter only cells with height at most t, and stop at the first t for which the bottom-right is reached.

def swim_brute(grid):
    n = len(grid)
    for t in range(n * n):
        if grid[0][0] > t:
            continue
        seen, q = {(0, 0)}, deque([(0, 0)])
        while q:
            r, c = q.popleft()
            if (r, c) == (n - 1, n - 1):
                return t
            for nr, nc in nbrs(grid, r, c):
                if (nr, nc) not in seen and grid[nr][nc] <= t:
                    seen.add((nr, nc))
                    q.append((nr, nc))

The grid holds the heights 0 to n² − 1, so there are up to n² levels, and each BFS costs O(n²): O(n⁴) in total. For n = 50 that is about 6 × 10^6 steps, which is acceptable, but for n = 500 it is about 6 × 10^10. Space is O(n²).

From brute force to the idea

  1. Find the waste. Each BFS restarts from the top-left and rediscovers the cells it reached for a lower t.
  2. Raise the level only as needed. Instead of trying every t, keep the cheapest frontier: the cell that can be entered at the lowest water level.
  3. Cost of reaching a cell. If you stand at a cell where the level had to be t, entering a neighbour needs max(t, height of the neighbour). A route's cost is the highest cell on it.
  4. Use a min-heap, as in Dijkstra. heap holds (level needed, row, column). Popping gives the cell reachable at the lowest level. The first time the bottom-right is popped, its level is the answer.
  5. Mark when pushing. A cell is added to seen when first pushed. The first cell to discover it is the one popped earliest, with the lowest t, so the cost it assigns is already the smallest possible.

The key idea: this is Dijkstra with "max" in place of "plus", because water must rise to the highest cell on the route.

The key idea

Dijkstra-style search where a path’s cost is its maximum height, not its sum.

Python solution

def swim_in_water(grid):
    n = len(grid)
    heap = [(grid[0][0], 0, 0)]
    seen = {(0, 0)}
    while heap:
        t, r, c = heappop(heap)  # lowest
        if (r, c) == (n - 1, n - 1):
            return t
        for nr, nc in nbrs(grid, r, c):
            if (nr, nc) not in seen:
                seen.add((nr, nc))
                tt = max(t, grid[nr][nc])
                heappush(heap, (tt, nr, nc))

def nbrs(g, r, c):  # in-grid neighbours
    R, C = len(g), len(g[0])
    for nr, nc in ((r+1, c), (r-1, c),
                   (r, c+1), (r, c-1)):
        if 0 <= nr < R and 0 <= nc < C:
            yield nr, nc

LeetCode adds the imports for you. To run this on your own machine, put this at the top: from heapq import heappush, heappop

In the interactive version each line lights up as the animation runs, and you can type your own input to see the algorithm handle it.

Complexity

ApproachTimeSpace
Try every water level (brute force)O(n⁴): up to n² levels, each with a BFS over n² cellsO(n²): the seen set and queue
Heap search (shown code)O(n² log n): each of the n² cells is pushed once, and each heap operation costs O(log n²) = O(log n)O(n²): the heap and the seen set

Edge cases

  • One cell ([[0]]): returns grid[0][0], here 0. A start cell of height 5 also gives 5, since you must wait for it.
  • High corners: the answer is at least the larger of the two corner heights, because both lie on every route.
  • A winding route: the 5 × 5 snake grid [[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]] returns 16.
  • Four directions only: diagonal moves are not allowed.
  • Imports: heappush and heappop, and the helper nbrs.

Common mistakes

  • Adding the heights along the route, which is the wrong measure for "highest cell on the route".
  • Using only the neighbour's height, grid[nr][nc], and forgetting the running maximum t.
  • Running a plain BFS (it counts steps, not water level).
  • Restricting moves to right and down, which misses routes that wind around high cells.
Your turn: the smoothest hiking route

Each cell is a height. The effort of a step is the absolute height difference between two neighbouring cells, and a route's effort is its largest step. Return the smallest possible effort from the top-left to the bottom-right (any rectangular grid). Describe what changes, then write it if you like.

Compare with our answer

It is the same "minimise the maximum" search, but a step's cost now depends on the pair of cells, not just the cell entered. That breaks marking at push time, because a later cell might reach a neighbour with a smaller step. Keep the best known effort per cell and skip stale entries.

def min_effort(h):
    R, C = len(h), len(h[0])
    best = {(0, 0): 0}
    heap = [(0, 0, 0)]
    while heap:
        t, r, c = heappop(heap)
        if (r, c) == (R - 1, C - 1):
            return t
        if t > best[(r, c)]:
            continue
        for nr, nc in nbrs(h, r, c):
            tt = max(t, abs(h[nr][nc] - h[r][c]))
            if tt < best.get((nr, nc), inf):
                best[(nr, nc)] = tt
                heappush(heap, (tt, nr, nc))

min_effort([[1,2,2],[3,8,2],[5,3,5]]) is 2. Time O(R·C·log(R·C)), space O(R·C).

A strong answer mentions: max instead of sum as the combining rule, the cost now depending on each step, and why a per-cell best value replaces the seen set.

Check what stuck

1. A network of toll roads joins your home to your destination. A trip's cost is the single largest toll you pay on it, and you can choose any route. Which approach fits best?

2. Why does the shown code run in O(n² log n) time?

3. A learner changes tt = max(t, grid[nr][nc]) to tt = grid[nr][nc]. Which input now returns a wrong answer?

Score 60% or more and the lesson is marked complete.