Graphs crash course ↗ · 105

778. Swim in Rising Water

You wait at time t until the water level reaches t; you can swim to adjacent cells whose elevation is ≤ t. Find the minimum t to reach the bottom-right corner. The insight: treat it as shortest-path where a path's cost is its maximum elevation — run Dijkstra with a min-heap.

● HardDijkstra / Min-HeapGrid BFSBinary Search + BFS/Union-FindTypeScript

PROBLEM What we're solving

You have an n×n integer grid where grid[r][c] is the elevation of that cell. At time t, you can occupy any cell whose elevation is ≤ t, and swim to any of its four neighbors that also has elevation ≤ t. Find the minimum time t to reach from (0,0) to (n-1,n-1).

Worked example.Consider the 4×4 grid:

 0  2  3  4
 1  9  7  5
10 11  8  6
12 13 14 15

One path: (0,0)→(1,0)→(2,0)→… but the bottleneck is cell (1,1)=9. The optimal route avoids that: right along the top and down the right column, with max elevation 15? No — a better path through the middle keeps the max at 15 anyway since the bottom-right is 15. The answer is 15.

KEY IDEA Path cost = maximum elevation along it

Insight →"Minimum time to swim through" = "minimum over all paths of the maximum cell elevation on that path." This is exactly minimax path — a classic Dijkstra variant. Replace edge weights with max(costSoFar, grid[nr][nc]) and run a standard min-heap. The first time you pop the destination, that cost is your answer, because the heap always expands the cheapest-max-so-far frontier first.

RECIPE Dijkstra with max-cost accumulation

  • 0 · Push start. Push [grid[0][0], 0, 0] onto the min-heap (cost = starting elevation, because we must wait at least that long).
  • 1 · Pop minimum cost.Extract the heap entry with the smallest cost. If it's already visited, skip it — a cheaper path already settled this cell.
  • 2 · Check goal. If the popped cell is (n-1, n-1), return its cost immediately (first pop is optimal in Dijkstra).
  • 3 · Expand neighbors. For each of the four adjacent cells (nr, nc) not yet visited, compute newCost = max(cost, grid[nr][nc]). Push [newCost, nr, nc]— the max tracks the highest elevation we've ever crossed on this path.
  • 4 · Repeat until the destination is popped.
Classic confusion →people sum elevations instead of taking the max. Summation gives total "wetness" accumulated, but the problem asks for the single time t when all cells on the path are simultaneously reachable. That is the maximum elevation on the path, not the sum.

COST Complexity & alternatives

BFS at each t (brute force)
O(n&sup4;)
Try every t from 0 to n²-1, run BFS each time.
Dijkstra / Min-Heap
O(n² log n)
n² cells, each pushed/popped once; heap ops are O(log n²) = O(log n).

Alternatives

Binary search + BFS/DFS: binary search on the answer t, then BFS to check reachability using only cells with elevation ≤ t. O(n² log n) overall — same asymptotic complexity but two passes per candidate.

Union-Find: process cells in elevation order and union them into components; stop when (0,0) and (n-1,n-1)share a component. Also O(n² α(n²)).

Pattern transfer →the "minimax path" pattern (Dijkstra with max instead of sum) applies to: Path With Minimum Effort (LC 1631 — same trick, cost = max abs difference), Minimum Cost to Make Array Equal, and any problem phrased as "minimize the maximum bottleneck along a path."

RUN IT Dijkstra: path cost = max elevation along it

step 0 / 41
STARTGrid loaded (4×4). Push top-left cell (elevation 0) to the min-heap. Min-heap key = max elevation along the path so far.
1function swimInWater(grid: number[][]): number {
2▶  const n = grid.length;
3  // Min-heap: [maxElevationSoFar, row, col]
4▶  const heap: [number, number, number][] = [[grid[0][0], 0, 0]];
5▶  const visited = Array.from({ length: n }, () => Array(n).fill(false));
6 
7  // Heap helpers (binary min-heap on index 0)
8  const push = (e: [number, number, number]) => {
9    heap.push(e);
10    let i = heap.length - 1;
11    while (i > 0) {
12      const p = (i - 1) >> 1;
13      if (heap[p][0] <= heap[i][0]) break;
14      [heap[p], heap[i]] = [heap[i], heap[p]];
15      i = p;
16    }
17  };
18  const pop = (): [number, number, number] => {
19    const top = heap[0];
20    const last = heap.pop()!;
21    if (heap.length > 0) {
22      heap[0] = last;
23      let i = 0;
24      while (true) {
25        let s = i, l = 2*i+1, r = 2*i+2;
26        if (l < heap.length && heap[l][0] < heap[s][0]) s = l;
27        if (r < heap.length && heap[r][0] < heap[s][0]) s = r;
28        if (s === i) break;
29        [heap[s], heap[i]] = [heap[i], heap[s]];
30        i = s;
31      }
32    }
33    return top;
34  };
35 
36  const DIRS = [[-1,0],[1,0],[0,-1],[0,1]];
37 
38  while (heap.length > 0) {
39    const [cost, r, c] = pop();
40    if (visited[r][c]) continue;
41    visited[r][c] = true;
42 
43    if (r === n - 1 && c === n - 1) return cost;  // reached bottom-right
44 
45    for (const [dr, dc] of DIRS) {
46      const nr = r + dr, nc = c + dc;
47      if (nr < 0 || nr >= n || nc < 0 || nc >= n || visited[nr][nc]) continue;
48      // Key insight: path cost = max elevation we must wait for
49      push([Math.max(cost, grid[nr][nc]), nr, nc]);
50    }
51  }
52 
53  return -1; // unreachable if valid input
54}
0
2
3
4
1
9
7
5
10
11
8
6
12
13
14
15
State
time (max elev): 0
cell: (0,0)
heap size: 1
current (just popped)chosen (visited)in heap (frontier)on shortest path
slowfast

TYPESCRIPT The solution, annotated

swimInWater.ts
function swimInWater(grid: number[][]): number {
  const n = grid.length;
  // Min-heap: [maxElevationSoFar, row, col]
  const heap: [number, number, number][] = [[grid[0][0], 0, 0]];
  const visited = Array.from({ length: n }, () => Array(n).fill(false));

  // Heap helpers (binary min-heap on index 0)
  const push = (e: [number, number, number]) => {
    heap.push(e);
    let i = heap.length - 1;
    while (i > 0) {
      const p = (i - 1) >> 1;
      if (heap[p][0] <= heap[i][0]) break;
      [heap[p], heap[i]] = [heap[i], heap[p]];
      i = p;
    }
  };
  const pop = (): [number, number, number] => {
    const top = heap[0];
    const last = heap.pop()!;
    if (heap.length > 0) {
      heap[0] = last;
      let i = 0;
      while (true) {
        let s = i, l = 2*i+1, r = 2*i+2;
        if (l < heap.length && heap[l][0] < heap[s][0]) s = l;
        if (r < heap.length && heap[r][0] < heap[s][0]) s = r;
        if (s === i) break;
        [heap[s], heap[i]] = [heap[i], heap[s]];
        i = s;
      }
    }
    return top;
  };

  const DIRS = [[-1,0],[1,0],[0,-1],[0,1]];

  while (heap.length > 0) {
    const [cost, r, c] = pop();
    if (visited[r][c]) continue;
    visited[r][c] = true;

    if (r === n - 1 && c === n - 1) return cost;  // reached bottom-right

    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]) continue;
      // Key insight: path cost = max elevation we must wait for
      push([Math.max(cost, grid[nr][nc]), nr, nc]);
    }
  }

  return -1; // unreachable if valid input
}

Reading it block by block

Lines 3–4 — initialize. The min-heap starts with the top-left cell at cost grid[0][0] (you must wait at least this long to even start). visited prevents re-processing settled cells.
Lines 6–26 — inline min-heap. A standard binary heap keyed on index 0 of the triple. push sifts up; pop swaps root with the last element and sifts down. Using an inline heap avoids any library dependency.
Lines 30–33 — pop and settle.Extract the minimum-cost entry. Skip if already visited (a later push may have been superseded by a cheaper one). Once popped and unvisited, this cell's cost is final — Dijkstra's invariant.
Line 35 — goal check. As soon as we pop (n-1, n-1), return its cost. Because we always pop the globally minimum-cost unvisited cell, the first time we settle the destination is provably optimal.
Lines 37–41 — expand neighbors. Math.max(cost, grid[nr][nc])is the load-bearing line: the path cost grows only when a new cell's elevation exceeds the current maximum. This accumulates the highest elevation we've crossed, which is exactly the time we'd need to wait.
Complexity → O(n² log n) time — each of the n² cells is pushed and popped at most once, and each heap operation is O(log n²) = O(log n). O(n²) space for the visited array and heap.

INTERVIEWFollow-ups they'll ask

  • "Can you do it without a priority queue?" Yes — binary search on t(range 0..n²-1) and run a simple BFS/DFS for each candidate. O(n² log n) total.
  • "What if the grid has duplicate elevations?" The algorithm is unchanged — duplicates are fine because we only care about the max elevation, not uniqueness.
  • "Why is Union-Find also valid?" Sort cells by elevation, add them in order and union each cell with its already-added neighbors. The answer is the elevation of the cell that first connects (0,0) to (n-1,n-1).
  • "How does this differ from standard Dijkstra?"Standard Dijkstra sums edge weights; here the "cost" to reach a cell is max(previous cost, cell elevation) instead of a sum. The heap invariant and correctness proof are identical.
  • "Trace the 4×4 example." Start by pushing [0,0,0]. Next pop: cost 0, expand right (cost 2) and down (cost 1). Pop cost 1 → (1,0), and so on. The heap always picks the cheapest frontier cell, routing around the peak at (1,1)=9.

OPTIMAL Dijkstra / Min-Heap

swimInWater.ts
function swimInWater(grid: number[][]): number {
  const n = grid.length;
  // Min-heap: [maxElevationSoFar, row, col]
  const heap: [number, number, number][] = [[grid[0][0], 0, 0]];
  const visited = Array.from({ length: n }, () => Array(n).fill(false));

  // Heap helpers (binary min-heap on index 0)
  const push = (e: [number, number, number]) => {
    heap.push(e);
    let i = heap.length - 1;
    while (i > 0) {
      const p = (i - 1) >> 1;
      if (heap[p][0] <= heap[i][0]) break;
      [heap[p], heap[i]] = [heap[i], heap[p]];
      i = p;
    }
  };
  const pop = (): [number, number, number] => {
    const top = heap[0];
    const last = heap.pop()!;
    if (heap.length > 0) {
      heap[0] = last;
      let i = 0;
      while (true) {
        let s = i, l = 2*i+1, r = 2*i+2;
        if (l < heap.length && heap[l][0] < heap[s][0]) s = l;
        if (r < heap.length && heap[r][0] < heap[s][0]) s = r;
        if (s === i) break;
        [heap[s], heap[i]] = [heap[i], heap[s]];
        i = s;
      }
    }
    return top;
  };

  const DIRS = [[-1,0],[1,0],[0,-1],[0,1]];

  while (heap.length > 0) {
    const [cost, r, c] = pop();
    if (visited[r][c]) continue;
    visited[r][c] = true;

    if (r === n - 1 && c === n - 1) return cost;  // reached bottom-right

    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]) continue;
      // Key insight: path cost = max elevation we must wait for
      push([Math.max(cost, grid[nr][nc]), nr, nc]);
    }
  }

  return -1; // unreachable if valid input
}
Complexity → O(n² log n) time — each of the n² cells is pushed and popped at most once, and each heap operation is O(log n²) = O(log n). O(n²) space for the visited array and heap.

ALT 1 Binary search on time + flood-fill reachability

O(n² log n) time · O(n²) space

Binary search the answer t; for each candidate, BFS over cells with elevation ≤ t and ask whether the exit is reachable.

approach-2.ts
function swimInWater(grid: number[][]): number {
  const n = grid.length;

  // Can we reach (n-1,n-1) from (0,0) using only cells with elevation <= t?
  const canReach = (t: number): boolean => {
    if (grid[0][0] > t) return false;
    const visited = Array.from({ length: n }, () => Array<boolean>(n).fill(false));
    const stack: [number, number][] = [[0, 0]];
    visited[0][0] = true;
    const DIRS = [[-1, 0], [1, 0], [0, -1], [0, 1]];

    while (stack.length > 0) {
      const [r, c] = stack.pop()!;
      if (r === n - 1 && c === n - 1) return true;
      for (const [dr, dc] of DIRS) {
        const nr = r + dr, nc = c + dc;
        if (nr < 0 || nr >= n || nc < 0 || nc >= n) continue;
        if (visited[nr][nc] || grid[nr][nc] > t) continue;
        visited[nr][nc] = true;
        stack.push([nr, nc]);
      }
    }
    return false;
  };

  // Answer lies in [max(grid[0][0], grid[n-1][n-1]), n*n - 1].
  // The exit cell elevation is always required, so seed lo with it too.
  let lo = Math.max(grid[0][0], grid[n - 1][n - 1]);
  let hi = n * n - 1;
  while (lo < hi) {
    const mid = (lo + hi) >> 1;        // floor midpoint
    if (canReach(mid)) hi = mid;        // mid works -> try smaller
    else lo = mid + 1;                  // mid fails -> need larger
  }
  return lo;                            // smallest t that connects start to exit
}
Note → Monotonic predicate: if you can cross at time t, you can cross at any t' > t— which is what makes binary search valid. Each check is an O(n²) flood fill and there are O(log n²) = O(log n) iterations. Easy to reason about and needs no priority queue, but it touches the grid O(log n) times versus Dijkstra's single pass.

ALT 2 Union-Find (Kruskal-style) on elevation order

O(n² α(n²)) time · O(n²) space

Add cells one at a time in increasing elevation, unioning each with already-added neighbors; the answer is the elevation at which start and exit first share a component.

approach-3.ts
class DSU {
  private parent: number[];
  private rank: number[];

  constructor(size: number) {
    this.parent = Array.from({ length: size }, (_, i) => i);
    this.rank = new Array<number>(size).fill(0);
  }

  find(x: number): number {
    while (this.parent[x] !== x) {
      this.parent[x] = this.parent[this.parent[x]]; // path halving
      x = this.parent[x];
    }
    return x;
  }

  union(a: number, b: number): void {
    const ra = this.find(a), rb = this.find(b);
    if (ra === rb) return;
    if (this.rank[ra] < this.rank[rb]) {
      this.parent[ra] = rb;
    } else if (this.rank[ra] > this.rank[rb]) {
      this.parent[rb] = ra;
    } else {
      this.parent[rb] = ra;
      this.rank[ra]++;
    }
  }

  connected(a: number, b: number): boolean {
    return this.find(a) === this.find(b);
  }
}

function swimInWater(grid: number[][]): number {
  const n = grid.length;
  const id = (r: number, c: number): number => r * n + c;

  // index cells by elevation so we can add them low -> high
  const order: number[][] = Array.from({ length: n * n }, () => [0, 0]);
  for (let r = 0; r < n; r++) {
    for (let c = 0; c < n; c++) {
      order[grid[r][c]] = [r, c]; // elevations are a permutation of 0..n*n-1
    }
  }

  const dsu = new DSU(n * n);
  const added = Array.from({ length: n }, () => Array<boolean>(n).fill(false));
  const DIRS = [[-1, 0], [1, 0], [0, -1], [0, 1]];
  const start = id(0, 0), end = id(n - 1, n - 1);

  for (let t = 0; t < n * n; t++) {
    const [r, c] = order[t];
    added[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) continue;
      if (added[nr][nc]) dsu.union(id(r, c), id(nr, nc));
    }
    if (dsu.connected(start, end)) return t; // t flooded the bridging cell
  }
  return -1; // unreachable for valid input
}
Note → Relies on the LeetCode constraint that elevations are a permutation of 0..n²-1, so order[t] directly maps an elevation to its cell — no sorting needed, hence O(n²) plus inverse Ackermann per union. If elevations could repeat, sort the cells first (adding an O(n² log n) term) and process equal elevations together before checking connectivity.

ALT 3 Brute force — try every time t, BFS each time

O(n&sup4;) time · O(n&sup2;) space

Walk t upward from 0; for each trun a fresh flood fill that may only step on cells with elevation ≤ t, and return the first t that reaches the exit — a correctness baseline before any binary search or heap.

approach-4.ts
function swimInWater(grid: number[][]): number {
  const n = grid.length;
  const DIRS = [[-1, 0], [1, 0], [0, -1], [0, 1]];

  // Can we reach (n-1,n-1) from (0,0) using only cells with elevation <= t?
  const canReach = (t: number): boolean => {
    if (grid[0][0] > t) return false;
    const visited = Array.from({ length: n }, () => Array<boolean>(n).fill(false));
    const stack: [number, number][] = [[0, 0]];
    visited[0][0] = true;
    while (stack.length > 0) {
      const [r, c] = stack.pop()!;
      if (r === n - 1 && c === n - 1) return true;
      for (const [dr, dc] of DIRS) {
        const nr = r + dr, nc = c + dc;
        if (nr < 0 || nr >= n || nc < 0 || nc >= n) continue;
        if (visited[nr][nc] || grid[nr][nc] > t) continue;
        visited[nr][nc] = true;
        stack.push([nr, nc]);
      }
    }
    return false;
  };

  // Linearly scan every candidate time; first one that connects start to exit wins.
  for (let t = 0; t < n * n; t++) {
    if (canReach(t)) return t;
  }
  return -1; // unreachable for valid input
}
Note → Correct but wasteful: it re-runs a full O(n²) flood fill for each of the O(n²) candidate times, giving O(n&sup4;). The reachability predicate is monotonic in t, so replace the linear scan with binary search to drop to O(n² log n), or skip it entirely with the Dijkstra single pass.

MNEMONIC The one-liner

"Dijkstra but swap sum for max — you wait for the highest peak you must cross, not the total."

TRIGGERS When you see ___ → reach for ___

"minimum time / cost to cross a grid"Dijkstra with max accumulation (minimax path)
"bottleneck path — minimize the maximum along it"min-heap, cost = max(prevCost, newCell)
reachability depends on water level / thresholdbinary search on answer + BFS, or Dijkstra
connect two nodes minimizing the max edge weightUnion-Find on sorted edges / cells

SKELETON The reusable shape

skeleton.ts
function swimInWater(grid: number[][]): number {
  const n = grid.length;
  const heap: [number, number, number][] = [[grid[0][0], 0, 0]];
  const visited = Array.from({ length: n }, () => Array(n).fill(false));
  // ... heap push/pop helpers ...
  const DIRS = [[-1,0],[1,0],[0,-1],[0,1]];

  while (heap.length > 0) {
    const [cost, r, c] = pop();
    if (visited[r][c]) continue;
    visited[r][c] = true;
    if (r === n - 1 && c === n - 1) return cost;
    for (const [dr, dc] of DIRS) {
      const nr = r + dr, nc = c + dc;
      if (outOfBounds || visited[nr][nc]) continue;
      push([Math.max(cost, grid[nr][nc]), nr, nc]);
    }
  }
  return -1;
}

FLASHCARDS Tap to flip

What does the heap key represent in this problem?
The maximum elevation (= minimum wait time) along the best path found so far to reach that cell — max(prevCost, grid[nr][nc]).
tap to flip
1 / 7
Answer to reveal explanations. No penalty for retries.Score: 0 / 9
QUESTION 01
What is the time complexity of the Dijkstra / min-heap approach?
QUESTION 02
When expanding a neighbor at (nr, nc), what value do we push onto the heap?
QUESTION 03
Why can we return immediately the first time we pop the destination cell?
QUESTION 04
For the 4×4 grid [[0,2,3,4],[1,9,7,5],[10,11,8,6],[12,13,14,15]], what is the answer?
QUESTION 05
Which alternative approach also achieves O(n² log n) for this problem?
QUESTION 06
If two cells have the same elevation, how does the algorithm handle them?
QUESTION 07
What is the starting cell's heap cost, and why?
QUESTION 08
#778 · Swim in Rising WaterModified Dijkstra where the cost of a path is the maximum cell elevation along it. A min-heap of (maxElevation, row, col) pops the cheapest frontier cell; return the cost when the bottom-right corner is reached.Which algorithmic approach does this primarily use?
QUESTION 09
#778 · Swim in Rising WaterModified Dijkstra where the cost of a path is the maximum cell elevation along it. A min-heap of (maxElevation, row, col) pops the cheapest frontier cell; return the cost when the bottom-right corner is reached.Which implementation correctly solves it?