Skip to content

Volume ITechnology

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.

A picture to hold in mind ​

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.

The general idea to take from this problem: Dijkstra works for any path cost that is monotonic, meaning it never improves 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)]  # (1)
        heap = [(grid[0][0], 0, 0)]           # (2) (time needed so far, r, c)

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

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

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

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

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

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

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

  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.

Line by line ​

(1) seen[r][c] marks cells whose best time is final.

(2) A heap of (time, r, c), smallest time first. The "time" for a cell is the earliest moment you could be standing there, which is the highest cell on the best path so far. You cannot even stand on the starting cell until the water reaches its height, so we start with grid[0][0].

(3) Take the cell you can reach soonest.

(4) Already final? Skip this out-of-date entry.

(5) Mark it final. As in Dijkstra's algorithm in 4.21.3, the first time a cell leaves the heap, its time cannot be beaten.

(6) Reached the bottom-right corner, so this time is the answer.

(7) Look at the four neighbours.

(8) The time to reach a neighbour through this cell is the larger of the time so far and the neighbour's own height. This is the one change from ordinary Dijkstra: a path's cost is not the sum of its steps but the highest point along it. max replaces +. Dijkstra still works, because a path's highest point can never go down as the path gets longer, just as a sum of non-negative times can never go down.

Edge cases ​

  • A 1 × 1 grid. The answer is its height, the moment you can stand on it.
  • The start cell is the highest cell. The answer is the start's height, because you must wait for it anyway.

Solution 2 — binary search plus flood fill ​

A different angle, and one that 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).

python
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.

Combine chapters into one PDF

Pick the chapters you want. They print in the order you pick them.

Volume I — Technology
Part 0 — Retention & Notation
Part 1 — Foundations of Computation
Part 2 — Operating Systems
2.1 The Kernel
2.2 Processes
2.3 Threads & Scheduling
2.4 Concurrency Under the Hood
2.5 Memory Management
2.6 File Systems
2.7 Input/Output
2.8 Linux for Engineers
2.9 Windows & macOS in Practice
Part 3 — Languages, Compilers & Runtimes
3.6 JavaScript & V8
3.7 TypeScript
3.8 Node.js Internals
3.13 Python & CPython
3.14 FastAPI & Production Python
Part 4 — Data Structures & Algorithms
4.0 Classic Problems — Before NeetCode
4.4 Arrays & Hashing — Problems
4.5 Two Pointers
4.6 Sliding Window
4.8 Stack — Problems
4.9 Linked List — Problems
4.11 Binary Search — Problems
4.13 Trees
4.14 Tree — Problems
4.15 Trie — Problems
4.17 Heap — Problems
4.18 Backtracking — Problems
4.19 Graphs
4.20 Graph — Problems
4.21 Advanced Graph — Problems
4.23 1-D DP — Problems
4.24 2-D DP — Problems
4.26 Greedy — Problems
4.27 Interval — Problems
4.28 Math & Geometry — Problems
4.30 Bit Manipulation — Problems
Part 5 — Networking & the Web
5.3 IP
5.4 Transport
5.6 HTTP
Part 6 — Frontend Engineering
6.1 Browser Internals
6.2 HTML & CSS Mastery
6.3 JavaScript in the Browser
6.4 React, from First Component to Full Shop
6.5 Frameworks & Rendering
6.8 UI Engineering & Patterns
Part 7 — Databases & Storage
7.2 SQL Mastery
7.3 Storage Engine Internals
7.4 Transactions
7.5 NoSQL Taxonomy
7.8 Analytics & Big Data
Part 8 — Security, Identity & Cryptography
8.2 Cryptography
8.3 Protocols of Trust
8.4 Identity: AuthN & AuthZ
8.5 Application Security
8.6 Infrastructure Security
Part 9 — Software Design (LLD)
9.2 OOP Foundations
9.3 Design Principles
9.4 Design Patterns
9.5 Concurrency
9.6 API Design
9.7 LLD Interview Machines
9.9 Node/Express Production Playbook
Part 10 — Distributed Systems & HLD
10.7 Consistency & Consensus
10.8 Messaging & Microservices
10.14 Caching
Building blocks from the design seat
Part 11 — System Design Case Studies
Part 12 — AI & ML Engineering
12.1 What AI Engineering Is
12.2 The Math You Need
12.3 Classical Machine Learning
12.4 Data for ML
12.5 Deep Learning
12.6 Embeddings & Vector Search
12.7 Transformers & LLMs
12.8 Building with LLMs
12.9 Retrieval-Augmented Generation
12.10 Agents
12.11 Adapting Models
12.12 Production AI
12.13 Multimodal AI
12.14 AI Security & Governance
12.15 Case Studies & Capstone
Part 13 — Cloud, DevOps & Infrastructure
13.11 Git, from First Commit to Team Workflow
Part 14 — Containers: Docker & Kubernetes
14.1 Foundations
14.2 Docker
14.3 Kubernetes
14.4 Kubernetes on Azure
Part 15 — The Craft & Career
Nothing picked yet