Swim In Rising Water

HARD✓ CHIP-TIMEDLC #778 — FULL STATEMENT ↗

The drill: Every cell in an n×n grid has an elevation, all distinct. Water starts at zero and keeps rising; you can only stand on a cell once its elevation is at or below the current water level. Find the water level that first opens a walking route corner to corner.

THE BRIEFING — THE FULL DRILL, IN MY OWN WORDS

A square grid assigns a distinct elevation to every cell. Water begins at level zero and rises over time, and a cell only becomes walkable once the current water level has reached or passed that cell's elevation.

Movement between walkable cells goes in the four orthogonal directions, and the trip has to start at the top-left cell and finish at the bottom-right one, stepping only on cells that are already underwater or at the surface.

The task is to find the smallest water level at which such a route first becomes possible — equivalently, the highest single cell that any route is forced to cross, minimized over every possible route.

EX 01

grid = [[0]]

→ 0

SINGLE CELL, NO SWIMMING NEEDED

EX 02

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

→ 2

2X2, FORCED ROUTE THROUGH THE HIGHEST CELL

EX 03

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

→ 3

2X2, START AND END ARE THE EXTREMES

grid side length runs roughly up to a few hundred cells
every elevation value in the grid is distinct
movement is the four orthogonal directions only
answer is the minimized worst elevation any route must cross

THE HINTS — TAKE ONLY WHAT YOU NEED

HINT 1 THE NUDGE

The answer isn't a sum along a route — it's the single tallest cell any route is forced to cross, minimized over every possible route.

HINT 2 THE STRUCTURE

Flip the framing: instead of asking "can I cross at time t" for every t, add cells to the grid in ascending order of elevation and watch when the start and the goal end up in the same connected blob.

HINT 3 ONE STEP FROM THE ANSWER

Union-Find, cell by increasing value: reveal a cell, union it with any already-revealed neighbor, and stop at the exact value where find(start) first equals find(goal) — that value is the answer.

COACH'S BOARD — THE PATTERN, STEP BY STEP

THE RISING TIDEPATTERN · UNION-FIND BY ELEVATIONgrid = [[0,1,2],[7,6,3],[8,5,4]]

STEP 1

Time 0: reveal cell (0,0), elevation 0 — the water starts here, at the lowest point on the whole grid.

STEP 1 / 6 · ← → WORK TOO

THE SPLITS — TWO PACES, TWO LANGUAGES

grind/swim-in-rising-water.py — RACE PACE

LANG ▸

PACE ▸

class Solution:
    def swimInWater(self, grid: List[List[int]]) -> int:
        n = len(grid)
        parent = list(range(n * n))

        def find(x):
            while parent[x] != x:
                parent[x] = parent[parent[x]]
                x = parent[x]
            return x

        def union(a, b):
            ra, rb = find(a), find(b)
            if ra != rb:
                parent[ra] = rb

        pos = [None] * (n * n)
        for r in range(n):
            for c in range(n):
                pos[grid[r][c]] = (r, c)

        revealed = [[False] * n for _ in range(n)]
        for t in range(n * n):
            r, c = pos[t]
            revealed[r][c] = 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 revealed[nr][nc]:
                    union(r * n + c, nr * n + nc)
            if find(0) == find(n * n - 1):
                return t
        return n * n - 1

TIME O(N²·Α(N²))SPACE O(N²)PYTHON · RACE PACE · 32 LN

class Solution:
    def swimInWater(self, grid: List[List[int]]) -> int:
        n = len(grid)
        best = [float('inf')]
        visited = [[False] * n for _ in range(n)]

        def dfs(r, c, cur_max):
            cur_max = max(cur_max, grid[r][c])
            if cur_max >= best[0]:
                return
            if r == n - 1 and c == n - 1:
                best[0] = cur_max
                return
            visited[r][c] = 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 visited[nr][nc]:
                    dfs(nr, nc, cur_max)
            visited[r][c] = False

        dfs(0, 0, 0)
        return best[0]

TIME O(4^(N²))SPACE O(N²)PYTHON · TRAINING PACE · 22 LN

class Solution {
    private int[] parent;

    public int swimInWater(int[][] grid) {
        int n = grid.length;
        parent = new int[n * n];
        for (int i = 0; i < n * n; i++) parent[i] = i;

        int[][] pos = new int[n * n][2];
        for (int r = 0; r < n; r++) {
            for (int c = 0; c < n; c++) {
                pos[grid[r][c]] = new int[] { r, c };
            }
        }

        boolean[][] revealed = new boolean[n][n];
        int[][] dirs = { {1, 0}, {-1, 0}, {0, 1}, {0, -1} };
        for (int t = 0; t < n * n; t++) {
            int r = pos[t][0], c = pos[t][1];
            revealed[r][c] = true;
            for (int[] d : dirs) {
                int nr = r + d[0], nc = c + d[1];
                if (nr >= 0 && nr < n && nc >= 0 && nc < n && revealed[nr][nc]) {
                    union(r * n + c, nr * n + nc);
                }
            }
            if (find(0) == find(n * n - 1)) return t;
        }
        return n * n - 1;
    }

    private int find(int x) {
        while (parent[x] != x) {
            parent[x] = parent[parent[x]];
            x = parent[x];
        }
        return x;
    }

    private void union(int a, int b) {
        int ra = find(a), rb = find(b);
        if (ra != rb) parent[ra] = rb;
    }
}

TIME O(N²·Α(N²))SPACE O(N²)JAVA · RACE PACE · 44 LN

class Solution {
    private int best;

    public int swimInWater(int[][] grid) {
        int n = grid.length;
        best = Integer.MAX_VALUE;
        boolean[][] visited = new boolean[n][n];
        dfs(grid, 0, 0, 0, visited);
        return best;
    }

    private void dfs(int[][] grid, int r, int c, int curMax, boolean[][] visited) {
        curMax = Math.max(curMax, grid[r][c]);
        if (curMax >= best) return;
        int n = grid.length;
        if (r == n - 1 && c == n - 1) {
            best = curMax;
            return;
        }
        visited[r][c] = true;
        int[][] dirs = { {1, 0}, {-1, 0}, {0, 1}, {0, -1} };
        for (int[] d : dirs) {
            int nr = r + d[0], nc = c + d[1];
            if (nr >= 0 && nr < n && nc >= 0 && nc < n && !visited[nr][nc]) {
                dfs(grid, nr, nc, curMax, visited);
            }
        }
        visited[r][c] = false;
    }
}

TIME O(4^(N²))SPACE O(N²)JAVA · TRAINING PACE · 30 LN

✓ CHIP-TIMED — ALL 4 SOLUTIONS RAN GREEN AGAINST SELF-AUTHORED CASES IN CI · JDK 21 · CPYTHON 3.12 · NOTHING PUBLISHES RED