Swim in Rising Water

Problem in Plain English

Given a square grid of elevations, find the smallest water level t at which a path from the top-left corner to the bottom-right corner exists using only cells whose elevation is at most t.

Problem Statement

You are given an n x n integer matrix grid where grid[i][j] is the elevation of that cell. At time t the water depth everywhere equals t, so you may stand on or swim through a cell exactly when its elevation is at most t.

Starting at (0, 0) and moving in the four cardinal directions, return the smallest t for which the destination (n - 1, n - 1) is reachable. Every elevation is unique and lies below n * n, so the answer always exists.

Constraints

n == grid.length
n == grid[i].length
1 <= n <= 50
0 <= grid[i][j] < n * n
Every value in grid is unique.

Examples

Example 1

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

At time 0 only the start is reachable. Both routes enter the destination of elevation 3, providing a lower bound of 3; the route through elevation 1 achieves that bound.

Example 2

Input: grid = [[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

Follow the top row 0 through 4, descend through 5 and 16, cross left through 15, 14, 13 and 12, descend through 11 and 10, then cross the bottom row through 9, 8, 7 and 6. Its maximum is 16. Below 16 the start component ends at elevation 5, whose other exit is elevation 21; it cannot reach the bottom region.

Example 3

Input: grid = [[0]]
Output: 0

The start is already the destination. No move is needed, and its elevation 0 is reachable immediately.

Example 4

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

The low destination does not make time 1 sufficient: the starting cell itself needs time 3. At 3 the route down through 0 and right through 1 is usable.

Intuition

A route is usable only after its highest cell is submerged. In Example 1, both routes must enter the destination of elevation 3, so even the route through elevation 1 needs time 3. A longer route can win if its highest cell is lower: the winding route in Example 2 avoids the ridge of elevations 17 through 24 and needs only 16. We can either test water levels in order, or guide the search by the highest elevation required to reach each cell.

Approaches

Linear Scan Plus BFS

Solution Details

Reveal Linear Scan Plus BFS: intuition, complexity, and code

Intuition

Waiting longer only ever opens more cells, so the first water level whose flooded cells connect start to finish is the answer. Scanning levels upward and flood-filling with BFS at each level is correct but re-explores the grid once per level.

Step-by-Step Logic

Try each integer level t from 0 through n squared minus 1. Reject a level if the start is higher; otherwise create fresh visited marks and a queue containing the start. BFS checks right, down, left and up, enqueuing only in-bounds unvisited cells at elevation at most t and marking them immediately. Return t when the destination is dequeued; an empty queue means this level fails.
Start at level t = 0 with grid = [[0, 2], [1, 3]]; BFS from (0, 0) reaches only itself since neighbours 2 and 1 exceed 0.
Raise to t = 1; BFS now also reaches (1, 0) with elevation 1, but (0, 1) at 2 and (1, 1) at 3 stay dry, so the target is unreached.
Raise to t = 2; BFS additionally reaches (0, 1), yet (1, 1) at 3 still blocks the destination.
Raise to t = 3; BFS reaches all four cells including (1, 1).
Return 3, the first level whose flood connects start to finish.

Why It Works

At a fixed level t, BFS visits exactly the connected component of the start among cells of elevation at most t: it inserts only legal adjacent cells, and every legal path is reached one step at a time. Marking on enqueue prevents revisits without losing any reachable cell. A start above t rejects immediately. The levels are tested from 0 upward, so every lower level has failed before the first successful one is returned. All elevations are below n squared, making the final level sufficient and the scan exhaustive.

Dry Run

Linear Scan Plus BFS: variable states at each step
level t	dequeued cell	newly enqueued / visited	queue after processing	outcome
0	(0,0)	none; elevations 2 and 1 exceed 0	[]	fail
1	(0,0)	(1,0)	[(1,0)]	continue
1	(1,0)	none; target 3 exceeds 1	[]	fail
2	(0,0)	(0,1), (1,0)	[(0,1),(1,0)]	continue
2	(0,1)	none; target 3 exceeds 2	[(1,0)]	continue
2	(1,0)	none; target 3 exceeds 2	[]	fail
3	(0,0)	(0,1), (1,0)	[(0,1),(1,0)]	continue
3	(0,1)	(1,1)	[(1,0),(1,1)]	continue
3	(1,0)	none; (1,1) already marked	[(1,1)]	continue
3	(1,1)	target popped; no expansion	[]	return 3

Complexity Analysis

Time Complexity

O(n^4)

Space Complexity

O(n^2)

Up to n squared levels each run BFS over at most n squared cells with four neighbors per cell, giving O(n^4) worst-case time. A fresh visited grid and queue use O(n^2) live auxiliary space; allocations repeat across levels but are not simultaneously retained. JavaScript keeps processed queue entries until that BFS finishes, still O(n^2). The caller grid is read only. A 50 by 50 grid has 2500 levels and 2500 cells, so this repeated search is deliberately the slower baseline.

Code

Solution.java

1import java.util.*;2
3class Solution {4    public int swimInWater(int[][] grid) {5        int n = grid.length;6        int[][] dirs = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};7        for (int t = 0; t < n * n; t++) {8            if (canReach(grid, t, n, dirs)) {9                return t;10            }11        }12        return n * n - 1;13    }14
15    private boolean canReach(int[][] grid, int t, int n, int[][] dirs) {16        if (grid[0][0] > t) {17            return false;18        }19        boolean[][] visited = new boolean[n][n];20        Queue<int[]> queue = new LinkedList<>();21        queue.offer(new int[]{0, 0});22        visited[0][0] = true;23        while (!queue.isEmpty()) {24            int[] cell = queue.poll();25            int r = cell[0];26            int c = cell[1];27            if (r == n - 1 && c == n - 1) {28                return true;29            }30            for (int[] d : dirs) {31                int nr = r + d[0];32                int nc = c + d[1];33                if (nr >= 0 && nr < n && nc >= 0 && nc < n && !visited[nr][nc] && grid[nr][nc] <= t) {34                    // Mark on enqueue: each legal cell joins this level's BFS once.35                    visited[nr][nc] = true;36                    queue.offer(new int[]{nr, nc});37                }38            }39        }40        return false;41    }42}

Hints

Hint 1

Think of the answer as a water level, not a path: at level t every cell up to elevation t is swimmable ground.

Hint 2

If the destination is reachable at level t, it stays reachable at every higher level, which means levels can be scanned rather than paths enumerated.

Hint 3

Run Dijkstra where a path costs its highest cell, always expanding the smallest-cost reachable cell until the destination pops.

Edge Cases

A 1 x 1 grid starts on the destination, so the answer is the single elevation with no moves.
The start or finish cell can hold the highest elevation on the route, forcing the whole answer up to that one value.
The cheapest route may wander away from the destination first to stay on low ground.

Common Mistakes and Interview Tips

Running plain BFS level by level without tracking the max elevation mixes short paths with low paths, since BFS minimises steps, not water level.
Copying this mark-on-insertion rule into general weighted Dijkstra is unsafe. Here all incoming moves share the destination elevation, which makes first discovery optimal; general graphs need distance relaxation and settlement on pop.
Pushing neighbours with the neighbour elevation instead of max(current cost, elevation) forgets the water already needed to get there.

Key Takeaway

When a path cost is the worst edge along it rather than a sum, Dijkstra with a maximising cost function finds the minimax route in a single guided search.