Swim in Rising Water — Dijkstra and Binary Search + BFS on a Grid [LC 778, Google, Amazon, Meta]

Problem Statement#

You are given an n x n integer grid. Each cell grid[r][c] represents the height of the platform at that cell. The water rises by 1 unit per time step starting at time 0. At time t, you can move from cell (r, c) to a 4-directional neighbour (r', c') if and only if t >= max(grid[r][c], grid[r'][c']) — both cells must be submerged enough to be passable. Return the minimum time to swim from (0, 0) to (n - 1, n - 1).

Constraints:

• 1 <= n <= 50
• 0 <= grid[i][j] < n^2
• All values are unique permutations of 0..n^2 - 1.

Example 1:

Input:  grid = [[0,2],[1,3]]
Output: 3
Explanation: At time 0 we are at (0,0)=0. To move to (1,1)=3 we need t >= 3.

Example 2:

Input:  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]]
Output: 16

Why This Problem Matters#

LeetCode 778 Swim in Rising Water is a FAANG hard interview classic at Google, Amazon, Meta, and Uber because it teaches the minimax-path-on-a-grid pattern. The right reduction transforms a confusing physics-flavoured prompt into a textbook shortest-path problem with a non-standard relaxation.

The same template solves at least three other top-asked problems:

• LeetCode 1631 Path With Minimum Effort — minimise the maximum absolute height difference between consecutive cells.
• LeetCode 1102 Path With Maximum Minimum Value — flip max to min.
• LeetCode 1102/1631 Cousins on graphs (not grids) — same pattern with adjacency lists.

In production, minimax grid paths model evacuation routing across flood zones, drone path planning where the worst altitude change matters more than total distance, and game-AI navigation where the worst danger level along a path is the cost. Whenever the optimisation is "the worst step decides the outcome," reach for this template.

The interview signal is layered: candidates who deliver Dijkstra with max(t, grid[nr][nc]) relax demonstrate they can adapt classical algorithms; those who also offer binary search + BFS or Kruskal's union-find variant show breadth. A single approach is enough to pass; multiple approaches earn senior signal.

The Core Insight#

The cost of a path is the maximum cell height encountered along it. We want the source-to-destination path that minimises this max. This is the same minimax pattern as the bottleneck shortest path on graphs, applied to a grid.

Three approaches all win, with different ergonomics:

• Dijkstra with max-relax — O(n^2 log n) time, O(n^2) space. Push (time, r, c) into a min-heap. Pop the smallest time; for each neighbour, push (max(time, grid[nr][nc]), nr, nc). The first pop of the destination is the answer. This is the cleanest single-pass solution.
• Binary search + BFS — O(n^2 log(n^2)) time, O(n^2) space. Binary search the answer T in [0, n^2 - 1]. For each T, BFS using only cells with height <= T. The smallest such T reaching the destination is the answer.
• Kruskal-style union-find — O(n^2 alpha(n^2)) time after sorting cells, O(n^2) space. Sort cells by height ascending. "Activate" them one by one and union with active neighbours. The first time (0, 0) and (n-1, n-1) become connected, the height of the cell that caused the union is the answer.

For n <= 50, all three pass comfortably. The interview default is Dijkstra because it generalises to weighted-edge graphs without modification.

Visual Dry Run#

grid = [[0,2], [1,3]]. Run Dijkstra from (0, 0).

Answer: 3. The minimax along the chosen path 0 -> 1 -> 3 is the cell value 3.

Solution (Optimal)#

Python — Dijkstra with max-relax#

import heapq
 
def swimInWater(grid):
    n = len(grid)
    seen = [[False] * n for _ in range(n)]
    heap = [(grid[0][0], 0, 0)]
    dirs = [(-1, 0), (1, 0), (0, -1), (0, 1)]
 
    while heap:
        t, r, c = heapq.heappop(heap)
        if seen[r][c]:
            continue
        seen[r][c] = True
        if r == n - 1 and c == n - 1:
            return t
        for dr, dc in dirs:
            nr, nc = r + dr, c + dc
            if 0 <= nr < n and 0 <= nc < n and not seen[nr][nc]:
                heapq.heappush(heap, (max(t, grid[nr][nc]), nr, nc))
    return -1

Python — Binary search + BFS#

from collections import deque
 
def swimInWater(grid):
    n = len(grid)
 
    def can_reach(T):
        if grid[0][0] > T:
            return False
        seen = [[False] * n for _ in range(n)]
        seen[0][0] = True
        q = deque([(0, 0)])
        while q:
            r, c = q.popleft()
            if r == n - 1 and c == n - 1:
                return True
            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 not seen[nr][nc] and grid[nr][nc] <= T:
                    seen[nr][nc] = True
                    q.append((nr, nc))
        return False
 
    lo, hi = grid[0][0], n * n - 1
    while lo < hi:
        mid = (lo + hi) // 2
        if can_reach(mid):
            hi = mid
        else:
            lo = mid + 1
    return lo

JavaScript — Dijkstra with max-relax#

function swimInWater(grid) {
    const n = grid.length;
    const seen = Array.from({ length: n }, () => new Array(n).fill(false));
    const heap = [[grid[0][0], 0, 0]];
    const dirs = [[-1, 0], [1, 0], [0, -1], [0, 1]];
 
    const popMin = () => {
        let mi = 0;
        for (let i = 1; i < heap.length; i++) if (heap[i][0] < heap[mi][0]) mi = i;
        return heap.splice(mi, 1)[0];
    };
 
    while (heap.length) {
        const [t, r, c] = popMin();
        if (seen[r][c]) continue;
        seen[r][c] = true;
        if (r === n - 1 && c === n - 1) return t;
        for (const [dr, dc] of dirs) {
            const nr = r + dr, nc = c + dc;
            if (nr >= 0 && nr < n && nc >= 0 && nc < n && !seen[nr][nc]) {
                heap.push([Math.max(t, grid[nr][nc]), nr, nc]);
            }
        }
    }
    return -1;
}

Complexity#

For n = 50, every approach runs in microseconds.

Common Mistakes#

• Using sum-Dijkstra unchanged. Standard relax dist[v] = dist[u] + w minimises path sums, not maxima. The relax must be max(t, grid[nr][nc]).
• Forgetting to include grid[0][0] in the initial time. At time 0 the start cell may already require a positive water level.
• Visiting a cell twice. Without the seen set you re-expand cells with stale times and waste work; lazy deletion via if seen after pop is fine.
• Off-by-one in the binary search bound. hi should be n*n - 1 (max grid value), and the predicate is monotone — once T works, all larger T also work.
• DFS instead of BFS in the reachability check. DFS works but is more bug-prone; BFS is safer and avoids recursion-limit issues.

Interview Tips#

• Lead with: "The path cost is the maximum cell height along the route. We want to minimise that maximum — minimax shortest path on a grid."
• Sketch all three approaches and pick Dijkstra with max-relax for cleanliness and best generality.
• Emphasise the relaxation change: "Replace + with max. The rest of Dijkstra is unchanged."
• Mention the union-find variant — sorting cells and unioning by height — as a clever offline alternative. It signals familiarity with the Kruskal pattern beyond MST.
• For grids, double-check directions and bounds; off-by-one bugs in the neighbour loop cost real points.

Follow-up Questions#

• Path With Minimum Effort (LC 1631)? Replace max(t, grid[nr][nc]) with max(t, abs(grid[nr][nc] - grid[r][c])). Same template.
• Path With Maximum Minimum Value (LC 1102)? Flip relaxation to min and use a max-heap. Answer is the largest minimum cell along any path.
• 8-directional movement? Add diagonal offsets; the algorithm is unchanged.
• Multiple sources or sinks? Push all sources into the heap with their initial values; stop at the first sink popped.
• Grid is too large to fit in memory? Use the union-find variant streaming cells in sorted order; only O(n^2) parent pointers needed.

Key Takeaways#

• LeetCode 778 Swim in Rising Water is a minimax-path problem on a grid; minimise the maximum cell height encountered.
• Dijkstra with max-relax is the cleanest single-pass solution: replace + with max(t, grid[nr][nc]).
• Binary search + BFS solves it in O(n^2 log(n^2)) and motivates monotonicity arguments well.
• Kruskal-style union-find delivers O(n^2 alpha) by activating cells in sorted height order until source and destination connect.
• The pattern generalises to LeetCode 1631 (Minimum Effort) and 1102 (Maximum Minimum Value).
• Companies that ask this: Google, Amazon, Meta, Microsoft, Bloomberg, Apple, Stripe, ByteDance.