Swim in Rising Water — Dijkstra Min-Heap Grid Interview

Problem Statement#

Given an N x N grid of integer elevations, return the minimum time to swim from (0,0) to (N-1,N-1). At time t, water level is t. You can step to a 4-neighbor only if both your cell and the neighbor are <= t.

Constraints:

• 1 <= N <= 50
• 0 <= grid[i][j] < N * N
• All values are unique

Input:  [[0,2],[1,3]]
Output: 3

Input:  [[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 is a Google and Amazon hard interview classic that hides Dijkstra behind a swim metaphor. It tests pattern recognition: can you see that minimizing max-on-path is exactly Dijkstra with a relaxed edge function?

This is a top heap FAANG interview problem because it forces you to articulate why Dijkstra works, why BFS does not, and why binary search plus union-find is also valid. Strong candidates show all three.

The Core Insight#

Replace Dijkstra's dist[v] = min(dist[v], dist[u] + w(u,v)) with dist[v] = min(dist[v], max(dist[u], grid[v])). The min-heap always pops the cell reachable by the lowest water level. The first time you pop (N-1, N-1), that level is the answer.

Visual Dry Run#

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

Solution (Optimal)#

import heapq
from typing import List
 
class Solution:
    def swimInWater(self, grid: List[List[int]]) -> int:
        n = len(grid)
        visited = [[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 r == n - 1 and c == n - 1:
                return t
            if visited[r][c]:
                continue
            visited[r][c] = True
            for dr, dc in dirs:
                nr, nc = r + dr, c + dc
                if 0 <= nr < n and 0 <= nc < n and not visited[nr][nc]:
                    heapq.heappush(heap, (max(t, grid[nr][nc]), nr, nc))
        return -1

class MinHeap {
    constructor() { this.h = []; }
    push(v) { this.h.push(v); this._up(this.h.length - 1); }
    pop() {
        const top = this.h[0], last = this.h.pop();
        if (this.h.length) { this.h[0] = last; this._down(0); }
        return top;
    }
    _up(i) {
        while (i > 0) {
            const p = (i - 1) >> 1;
            if (this.h[i][0] < this.h[p][0]) { [this.h[i], this.h[p]] = [this.h[p], this.h[i]]; i = p; }
            else break;
        }
    }
    _down(i) {
        const n = this.h.length;
        while (true) {
            const l = 2 * i + 1, r = 2 * i + 2;
            let m = i;
            if (l < n && this.h[l][0] < this.h[m][0]) m = l;
            if (r < n && this.h[r][0] < this.h[m][0]) m = r;
            if (m === i) break;
            [this.h[i], this.h[m]] = [this.h[m], this.h[i]];
            i = m;
        }
    }
    get size() { return this.h.length; }
}
 
var swimInWater = function(grid) {
    const n = grid.length;
    const visited = Array.from({ length: n }, () => new Array(n).fill(false));
    const heap = new MinHeap();
    heap.push([grid[0][0], 0, 0]);
    const dirs = [[-1, 0], [1, 0], [0, -1], [0, 1]];
    while (heap.size) {
        const [t, r, c] = heap.pop();
        if (r === n - 1 && c === n - 1) return t;
        if (visited[r][c]) continue;
        visited[r][c] = true;
        for (const [dr, dc] of dirs) {
            const nr = r + dr, nc = c + dc;
            if (nr >= 0 && nr < n && nc >= 0 && nc < n && !visited[nr][nc]) {
                heap.push([Math.max(t, grid[nr][nc]), nr, nc]);
            }
        }
    }
    return -1;
};

Time: O(N^2 log N) — every cell pushed at most a few times; each heap op is log(N^2) = 2 log N. Space: O(N^2) — visited and heap.

Common Mistakes#

• Using BFS — does not respect the "max along path" cost function.
• Forgetting to push max(t, grid[nr][nc]) — pushing only the neighbor height undercounts the time.
• Marking visited at push time can be wrong here; mark on pop after the cheaper relaxation wins.
• Returning t at the wrong moment; you must return when popping the destination, not when pushing it.
• Treating it as 0/1 BFS — the cost is not 0 or 1.

Interview Tips#

• Verbalize the reduction to Dijkstra with max instead of +.
• Mention the binary search plus DFS alternative as a sanity check.
• Discuss union-find solution: sort cells, union as water rises, stop when start and end connect.
• Note that all three approaches give the same answer — useful for cross-validation.

Follow-up Questions#

• Solve with binary search plus DFS. Hint: binary search on time, DFS to check connectivity.
• Solve with Kruskal-style union-find. Hint: process cells in increasing elevation.
• What if elevations are not unique? Hint: same algorithm, ties broken arbitrarily.
• What if you can swim diagonally? Hint: 8 directions; same Dijkstra logic.
• Find the actual path, not just the time. Hint: store predecessors during heap pops.

Key Takeaways#

• LeetCode 778 Swim in Rising Water is Dijkstra with max instead of +.
• The min-heap pops cells in increasing reachable water level.
• Time: O(N^2 log N). Space: O(N^2).
• Three valid approaches: Dijkstra, binary search plus DFS, union-find — know all three.
• This is a textbook minimum-bottleneck-path problem.
• BFS does not work because edge costs are not uniform.
• A favorite hard problem in Google heap FAANG interview rounds.