4.21.4 — Swim in Rising Water

LeetCode 778 · Hard

The problem

Each cell of an n × n grid has an elevation. At time t the water level is t, and you may swim between adjacent cells if both are at or below the water level. Return the earliest time you can reach the bottom-right corner from the top-left.

grid = [[0,2],[1,3]]   →  3

In plain English, you are placed on a 2D grid of terrain where each cell has a height. At time t=0, the water level is 0, and it rises by 1 unit every unit of time. You can only swim to a neighboring cell if the water level has risen enough to completely cover both your current cell and the neighboring cell. What is the absolute earliest time you can reach the bottom-right corner?

You need to reach the cell with elevation 3, so you cannot arrive before time 3.

The pattern

The cost of a route is not the sum of its cells. You can swim through a route as soon as the water covers its highest cell, so:

\text{cost of a path} = \max(\text{elevations along it})

And the answer is the path whose maximum is smallest — a minimax path.

The ELI5 Analogy

Imagine you are driving an off-road vehicle across a desert from the top-left to the bottom-right, but there are massive sand dunes everywhere. Your vehicle has a "max dune height" it can climb. If you pick a path that has twenty small 5-foot dunes, your vehicle only needs a rating of 5. But if you pick a shortcut path that is mostly flat but has one massive 50-foot dune, you need a rating of 50 to survive that route! You want to buy the cheapest vehicle possible (lowest rating). So you don't care about the sum of the dunes on a path; you only care about the single highest dune on that path. You want the path where the highest dune is as small as possible.

That is still Dijkstra. Dijkstra never actually requires addition; it requires that extending a path cannot make it cheaper. Replacing "sum so far plus edge weight" with "maximum so far versus cell elevation" keeps that property, because a maximum never decreases.

This is the generalisation worth taking from the problem: Dijkstra works for any path cost that is monotonic — never improved by adding another step. Sum, maximum, and multiplying probabilities below 1 all qualify.

Solution 1 — Dijkstra with a maximum

Python

import heapq

class Solution:
    def swimInWater(self, grid: List[List[int]]) -> int:
        n = len(grid)
        seen = [[False] * n for _ in range(n)]
        heap = [(grid[0][0], 0, 0)]           # (time needed so far, r, c)

        while heap:
            time, r, c = heapq.heappop(heap)
            if seen[r][c]:
                continue
            seen[r][c] = True

            if r == n - 1 and c == n - 1:
                return time                    # first arrival is optimal

            for nr, nc in ((r+1,c), (r-1,c), (r,c+1), (r,c-1)):
                if 0 <= nr < n and 0 <= nc < n and not seen[nr][nc]:
                    heapq.heappush(heap, (max(time, grid[nr][nc]), nr, nc))

        return -1

TypeScript

function swimInWater(grid: number[][]): number {
  const n = grid.length;
  const seen = Array.from({ length: n }, () => new Array(n).fill(false));
  const heap = new MinHeap<[number, number, number]>((e) => e[0]);
  heap.push([grid[0][0], 0, 0]);

  while (heap.size) {
    const [time, r, c] = heap.pop()!;
    if (seen[r][c]) continue;
    seen[r][c] = true;

    if (r === n - 1 && c === n - 1) return time;

    for (const [nr, nc] of [[r+1,c],[r-1,c],[r,c+1],[r,c-1]] as [number,number][]) {
      if (nr >= 0 && nr < n && nc >= 0 && nc < n && !seen[nr][nc]) {
        heap.push([Math.max(time, grid[nr][nc]), nr, nc]);
      }
    }
  }

  return -1;
}

max(time, grid[nr][nc]) replaces the usual cost + weight. That single substitution turns Dijkstra from a shortest-sum algorithm into a smallest-maximum one.

The start cost is grid[0][0], not 0 — you must wait for the water to cover the starting cell before you can move at all.

Returning on first arrival is the same guarantee as ordinary Dijkstra: the first pop of a node is its optimal value.

O(n^2 \log n) time, O(n^2) space.

Solution 2 — binary search plus flood fill

A different angle worth knowing, because it is often easier to reach under pressure.

Ask: at time t, can I get from corner to corner? That is a plain flood fill over the cells with elevation ≤ t.

And the answers are monotonic — if you can swim at time t, you can swim at any later time, because the water only rises. So binary search the time (4.11.3).

def swimInWater(self, grid):
    n = len(grid)

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

    lo, hi = grid[0][0], n * n - 1
    while lo < hi:
        mid = (lo + hi) // 2
        if reachable(mid): hi = mid
        else: lo = mid + 1
    return lo

O(n^2 \log(n^2)), which is O(n^2 \log n) — the same as Dijkstra. The elevations are a permutation of 0 … n²−1, which is what bounds the search range.

Say both. Binary search plus a reachability check is a pattern that solves many "smallest threshold that makes something possible" problems, and recognising that this is one of them is worth as much as the Dijkstra version.

Solution 3 — union-find

Sort the cells by elevation and add them one at a time, unioning each with its already-added neighbours. The answer is the elevation at which the two corners first become connected.

O(n^2 \log n) for the sort, then effectively linear. It is the neatest of the three and the least obvious.

It is also the same shape as Kruskal's algorithm in 4.21.2 — process in increasing weight order and union — which is a nice connection to draw.

Where this goes next

The minimax-path idea shows up more often than it looks:

• Path with Minimum Effort (LeetCode 1631) — minimise the largest difference between adjacent cells on the route. Same three solutions.
• Minimum Score of a Path — minimise, then take the smallest edge on the route.
• Bottleneck shortest path in networking — maximise the smallest bandwidth along a route, which is the mirror image.

The recognition cue: the path cost is a maximum or a minimum along the route rather than a sum. Dijkstra still applies; only the combine step changes.

What the interviewer will push on

"Why does Dijkstra still work when the cost is a maximum?" Because a maximum never decreases as the path grows, so extending a path cannot improve it — which is the only property Dijkstra needs.

"Why is the start cost grid[0][0]?" You cannot move until the water covers the starting cell.

"Can you do it without a heap?" Binary search the time plus a flood fill, or union-find by increasing elevation.

"Which of the three would you write?" Any; say the complexities are equal and that binary search is the easiest to get right under pressure.

"What if you had to minimise the sum instead?" Ordinary Dijkstra, cost + grid[nr][nc].

One thing to volunteer: state the cost model explicitly before coding. "The cost of a path is the maximum cell on it, not the sum." Everything downstream depends on that sentence, and it is where wrong solutions come from.

Next: 4.21.5 Alien Dictionary — where the difficulty is building the graph, not searching it.