Swim in Rising Water

Picture a square pool. Water rises over time. Each cell has a height. You can only move into a cell once the water level reaches its height. You want to swim from the top-left corner to the bottom-right corner. The question is the earliest time you can arrive. This looks like a maze, but it is really a clever shortest path problem.

🎯 The Problem

Water rises over a grid of heights, and you want the earliest time you can swim across.

• The grid is n by n. Each cell holds a number, its elevation, which is the height of that cell.
• At time t, the water level is t. You can stand on any cell whose elevation is at most t.
• You start at the top-left cell (0, 0) and want to reach the bottom-right cell.
• You may move up, down, left, or right. Swimming between cells takes no time.
• The only limit is the water level. Return the least time when a path from start to end exists.

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

Explanation: At time 3 the water covers every cell on the path.
You go (0,0) -> (0,1) -> (1,1), and the highest cell on it is 3.

The cost of a path is the highest elevation along it. We want the path whose highest cell is as small as possible. That is called a minimax path. Minimax means we minimize the maximum cell we must cross. Here is the grid as a small graph of moves.

🐢 Approach 1: Binary Search Plus BFS (Brute Force)

The idea in one line: guess a water level, test if you can cross at that level, then narrow the guess.

The idea:

• Binary search means guess a value, check if it works, then cut the range in half.
• Guess a water level t. The answer sits between the smallest and largest elevation.
• For each guess, run a breadth-first search. BFS explores the grid level by level from the start.

How it works:

• The BFS only steps into cells whose elevation is at most t.
• If BFS reaches the end, then t is enough, so try a smaller t.
• If not, try a bigger t.

Why it is weak:

• It runs a fresh BFS for every guess.
• The same cells get explored again and again across guesses.
• One pass can do the same work.

Here is the binary-search-plus-BFS code:

from collections import deque
def swim_in_water(grid):
    n = len(grid)
    def can(t):
        if grid[0][0] > t: return False
        q, seen = deque([(0, 0)]), {(0, 0)}
        while q:
            r, c = q.popleft()
            if r == n - 1 and c == 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)); q.append((nr, nc))
        return False
    lo, hi = grid[0][0], n * n
    while lo < hi:
        mid = (lo + hi) // 2
        if can(mid): hi = mid
        else: lo = mid + 1
    return lo

⚡ Approach 2: Dijkstra-Style Search (Best)

The idea in one line: always step to the reachable cell whose worst crossing so far is smallest, until you reach the end.

The idea:

• This is shaped like Dijkstra’s algorithm, which normally finds the path with the smallest total cost.
• Change the cost rule. Instead of adding costs along the path, take the maximum cell on the path.
• So the cost of reaching a cell is the highest elevation you had to cross to get there.

How it works:

• Use a min-heap that always hands you the cell with the smallest such cost.
• Push the top-left cell with its own elevation as the cost.
• Pull the cell with the smallest cost. That cost is the earliest time to reach it.
• For each neighbor, its cost is the larger of the current cost and that neighbor’s elevation.
• Push each neighbor with that new cost. Mark cells visited so none is processed twice.
• The first time you pull the bottom-right cell, its cost is the earliest arrival time.

Why it is fast:

• One sweep, no repeated BFS runs.
• Each cell is settled once, and each heap step costs about log of the cell count.

Here is the order the heap pulls cells on the example. Each label shows the reach cost, the highest cell crossed so far.

Steps to Solve

1. Make a min-heap of (cost, row, col). Push the start with its own elevation as the cost.
2. Keep a visited grid so each cell is processed once.
3. Pull the cell with the smallest cost. If it is the end cell, return its cost.
4. Mark it visited.
5. For each of the four neighbors not visited, the new cost is the larger of the current cost and that neighbor’s elevation.
6. Push each neighbor with its new cost. Repeat until the end is pulled.

#include <stdio.h>

#define N 2

int grid[N][N] = {{0,2},{1,3}};
int visited[N][N];

// simple min-heap of (cost, r, c)
int hc[64], hr[64], hcc[64];
int heapSize = 0;

void push(int cost, int r, int c) {
    int i = heapSize++;
    hc[i] = cost; hr[i] = r; hcc[i] = c;
    while (i > 0) {                 // bubble up
        int p = (i - 1) / 2;
        if (hc[p] <= hc[i]) break;
        int tc = hc[p]; hc[p] = hc[i]; hc[i] = tc;
        int tr = hr[p]; hr[p] = hr[i]; hr[i] = tr;
        int tcc = hcc[p]; hcc[p] = hcc[i]; hcc[i] = tcc;
        i = p;
    }
}

void pop(int *cost, int *r, int *c) {
    *cost = hc[0]; *r = hr[0]; *c = hcc[0];
    heapSize--;
    hc[0] = hc[heapSize]; hr[0] = hr[heapSize]; hcc[0] = hcc[heapSize];
    int i = 0;
    while (1) {                     // bubble down
        int l = 2*i+1, rr = 2*i+2, s = i;
        if (l < heapSize && hc[l] < hc[s]) s = l;
        if (rr < heapSize && hc[rr] < hc[s]) s = rr;
        if (s == i) break;
        int tc = hc[s]; hc[s] = hc[i]; hc[i] = tc;
        int tr = hr[s]; hr[s] = hr[i]; hr[i] = tr;
        int tcc = hcc[s]; hcc[s] = hcc[i]; hcc[i] = tcc;
        i = s;
    }
}

int main(void) {
    int dr[] = {-1,1,0,0}, dc[] = {0,0,-1,1};
    push(grid[0][0], 0, 0);
    int ans = 0;
    while (heapSize > 0) {
        int cost, r, c;
        pop(&cost, &r, &c);
        if (visited[r][c]) continue;
        visited[r][c] = 1;
        if (r == N-1 && c == N-1) { ans = cost; break; }
        for (int d = 0; d < 4; d++) {
            int nr = r + dr[d], nc = c + dc[d];
            if (nr<0||nc<0||nr>=N||nc>=N||visited[nr][nc]) continue;
            int nextCost = cost > grid[nr][nc] ? cost : grid[nr][nc];
            push(nextCost, nr, nc);   // max of path so far and this cell
        }
    }
    printf("%d\n", ans);
    return 0;
}

3

#include <iostream>
#include <vector>
#include <queue>
#include <tuple>
using namespace std;

int main() {
    vector<vector<int>> grid = {{0,2},{1,3}};
    int n = grid.size();
    vector<vector<bool>> visited(n, vector<bool>(n, false));

    priority_queue<tuple<int,int,int>,
        vector<tuple<int,int,int>>, greater<>> pq;
    pq.push({grid[0][0], 0, 0});  // (cost, row, col)

    int dr[] = {-1,1,0,0}, dc[] = {0,0,-1,1};
    int ans = 0;
    while (!pq.empty()) {
        auto [cost, r, c] = pq.top(); pq.pop();
        if (visited[r][c]) continue;
        visited[r][c] = true;
        if (r == n-1 && c == n-1) { ans = cost; break; }
        for (int d = 0; d < 4; d++) {
            int nr = r + dr[d], nc = c + dc[d];
            if (nr<0||nc<0||nr>=n||nc>=n||visited[nr][nc]) continue;
            int nextCost = max(cost, grid[nr][nc]);  // highest cell so far
            pq.push({nextCost, nr, nc});
        }
    }
    cout << ans << endl;
    return 0;
}

3

import java.util.*;

public class Swim {
    public static void main(String[] args) {
        int[][] grid = {{0,2},{1,3}};
        int n = grid.length;
        boolean[][] visited = new boolean[n][n];

        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[0] - b[0]);
        pq.offer(new int[]{grid[0][0], 0, 0});  // (cost, row, col)

        int[] dr = {-1,1,0,0}, dc = {0,0,-1,1};
        int ans = 0;
        while (!pq.isEmpty()) {
            int[] cur = pq.poll();
            int cost = cur[0], r = cur[1], c = cur[2];
            if (visited[r][c]) continue;
            visited[r][c] = true;
            if (r == n-1 && c == n-1) { ans = cost; break; }
            for (int d = 0; d < 4; d++) {
                int nr = r + dr[d], nc = c + dc[d];
                if (nr<0||nc<0||nr>=n||nc>=n||visited[nr][nc]) continue;
                int nextCost = Math.max(cost, grid[nr][nc]);  // highest cell
                pq.offer(new int[]{nextCost, nr, nc});
            }
        }
        System.out.println(ans);
    }
}

3

import heapq

def swim_in_water(grid):
    n = len(grid)
    visited = [[False] * n for _ in range(n)]
    heap = [(grid[0][0], 0, 0)]      # (cost, row, col)

    while heap:
        cost, r, c = heapq.heappop(heap)   # smallest reach cost
        if visited[r][c]:
            continue
        visited[r][c] = True
        if r == n - 1 and c == n - 1:
            return cost                    # reached the end
        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 visited[nr][nc]:
                next_cost = max(cost, grid[nr][nc])  # highest cell so far
                heapq.heappush(heap, (next_cost, nr, nc))
    return -1


grid = [[0, 2], [1, 3]]
print(swim_in_water(grid))

3

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

  while (heap.length > 0) {
    heap.sort((a, b) => a[0] - b[0]);   // smallest cost to the front
    const [cost, r, c] = heap.shift();
    if (visited[r][c]) continue;
    visited[r][c] = true;
    if (r === n - 1 && c === n - 1) return cost; // reached the end
    for (const [dr, dc] of [[-1, 0], [1, 0], [0, -1], [0, 1]]) {
      const nr = r + dr, nc = c + dc;
      if (nr >= 0 && nc >= 0 && nr < n && nc < n && !visited[nr][nc]) {
        const nextCost = Math.max(cost, grid[nr][nc]); // highest cell so far
        heap.push([nextCost, nr, nc]);
      }
    }
  }
  return -1;
}

const grid = [[0, 2], [1, 3]];
console.log(swimInWater(grid));

3

Let us read the Python version line by line and see the reason behind each part.

visited = [[False] * n for _ in range(n)]
heap = [(grid[0][0], 0, 0)]

visited stops us from processing the same cell twice. The heap starts with the top-left cell. Its cost is its own elevation, because we must wait for the water to reach the start before we can stand on it. We store (cost, row, col) so the heap orders by cost first.

cost, r, c = heapq.heappop(heap)
if visited[r][c]:
    continue
visited[r][c] = True

We pull the cell with the smallest reach cost. If we already settled it, we skip this stale copy. Otherwise this cost is the earliest time we can be on this cell. That is true because the heap always hands us the cheapest reachable cell next, just like Dijkstra’s.

if r == n - 1 and c == n - 1:
    return cost

The moment we pull the bottom-right cell, its cost is the earliest arrival time for the whole grid. So we return it right away.

next_cost = max(cost, grid[nr][nc])
heapq.heappush(heap, (next_cost, nr, nc))

This is the minimax twist. To reach the neighbor, the water must cover both the path so far and the neighbor’s own elevation. So we take the larger of the two with max. We do not add. We push the neighbor with this new cost so the heap can order it correctly.

⏱️ Time and Space Complexity

The grid has n² cells. The Dijkstra-style search pushes each cell a constant number of times and each heap operation costs about log of the number of cells. So the total time is O(n² log n). The space holds the visited grid and the heap, which is O(n²). The binary search plus BFS approach is also good, at O(n² log n), but it repeats a full BFS for every guess.

🧩 Key Takeaways

• ✅ The cost of a path is its highest cell, so we want the minimax path.
• ✅ A Dijkstra-style min-heap finds it by always pulling the cell with the smallest reach cost.
• ✅ The reach cost of a neighbor is the max of the current cost and the neighbor’s elevation.
• ✅ The first time you pull the end cell, its cost is the earliest arrival time.
• ✅ It runs in O(n² log n) time, the same as binary search plus BFS but in one pass.

🚀 What’s Next?

• Network Delay Time
• Cheapest Flights Within K Stops