Swim in Rising Water

HardGraphs · Minimax Path (Dijkstra)🧩 Shortest Paths LeetCode #778 ↗Updated Oct 30, 2026

Problem

An n × n grid holds distinct elevations. At time t the water level is t, and you may move (instantly, 4-directionally) between cells whose elevations are both ≤ t. Return the earliest time at which you can get from the top-left cell to the bottom-right cell.

Input[[0,2],[1,3]]Output3

Input

[[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]]

Output16

1 ≤ n ≤ 50 · 0 ≤ grid[i][j] < n² · all values distinct

Try it yourself

Java

class Solution {
    public int swimInWater(int[][] grid) {
        
    }
}

Your code is saved in this browser.Submit on LeetCode ↗

Key insight

The answer is the path that minimises its highest cell (a minimax path). Dijkstra works with “path cost = max elevation so far”, because extending a path can never lower that cost.

PatternShortest Paths

Instinct Weighted edges plus "minimum cost, time or effort to reach" - grab a min-heap and always expand the cheapest unsettled node next (Dijkstra).

Memory hack Pop the cheapest, skip the stale, relax the rest - Dijkstra is a ripple in a pond that touches near shores before far ones.

Open the Shortest Paths guide →

Approaches

Brute ForceTry Every Water Level + DFS

Time O(n⁴)Space O(n²)

For t = max(start, end), t+1, ... run a DFS that only enters cells with elevation ≤ t; the first t that reaches the corner is the answer. Up to n² levels × O(n²) DFS.

Java

public int swimInWater(int[][] grid) {
    int n = grid.length;
    for (int t = Math.max(grid[0][0], grid[n - 1][n - 1]); ; t++)
        if (reach(grid, 0, 0, t, new boolean[n][n])) return t;
}
private boolean reach(int[][] g, int r, int c, int t, boolean[][] seen) {
    int n = g.length;
    if (r < 0 || c < 0 || r >= n || c >= n || seen[r][c] || g[r][c] > t) return false;
    if (r == n - 1 && c == n - 1) return true;
    seen[r][c] = true;
    return reach(g, r + 1, c, t, seen) || reach(g, r - 1, c, t, seen)
        || reach(g, r, c + 1, t, seen) || reach(g, r, c - 1, t, seen);
}

Obviously correct, but repeats a full flood fill for every level.

BetterBinary Search on Time + DFS

Time O(n² log n)Space O(n²)

Reachability is monotonic: if you can swim at time t, you can at any later time. So binary-search the smallest feasible t in [max(start, end), n²-1], using the same DFS as the check.

Java

public int swimInWater(int[][] grid) {
    int n = grid.length;
    int lo = Math.max(grid[0][0], grid[n - 1][n - 1]), hi = n * n - 1;
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (reach(grid, 0, 0, mid, new boolean[n][n])) hi = mid; // feasible: go lower
        else lo = mid + 1;
    }
    return lo;
}
private boolean reach(int[][] g, int r, int c, int t, boolean[][] seen) {
    int n = g.length;
    if (r < 0 || c < 0 || r >= n || c >= n || seen[r][c] || g[r][c] > t) return false;
    if (r == n - 1 && c == n - 1) return true;
    seen[r][c] = true;
    return reach(g, r + 1, c, t, seen) || reach(g, r - 1, c, t, seen)
        || reach(g, r, c + 1, t, seen) || reach(g, r, c - 1, t, seen);
}

Only O(log n) flood fills, but still several full passes over the grid.

OptimalDijkstra (Min-Heap on Max Elevation)

Time O(n² log n)Space O(n²)

Grow the reachable region from the start, always entering the lowest frontier cell; the key of a cell is the max elevation on the path to it. The first time the corner is popped, its key is the minimum possible water level.

Java

public int swimInWater(int[][] grid) {
    int n = grid.length;
    int[] dirs = {-1, 0, 1, 0, -1};
    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}); // {max elevation so far, r, c}
    while (!pq.isEmpty()) {
        int[] cur = pq.poll();
        int t = cur[0], r = cur[1], c = cur[2];
        if (visited[r][c]) continue;
        visited[r][c] = true;
        if (r == n - 1 && c == n - 1) return t;
        for (int d = 0; d < 4; d++) {
            int nr = r + dirs[d], nc = c + dirs[d + 1];
            if (nr >= 0 && nr < n && nc >= 0 && nc < n && !visited[nr][nc])
                pq.offer(new int[]{Math.max(t, grid[nr][nc]), nr, nc});
        }
    }
    return -1; // unreachable: the grid is connected
}

One pass with early exit — the standard answer for minimax paths.

Pro tip

Values are a permutation of 0..n²-1: adding cells in elevation order to a Union-Find until start and end connect gives O(n² α(n)).

At a glance

Level	Approach	Time	Space
Brute Force	Try Every Water Level + DFS	`O(n⁴)`	`O(n²)`
Better	Binary Search on Time + DFS	`O(n² log n)`	`O(n²)`
Optimal	Dijkstra (Min-Heap on Max Elevation)	`O(n² log n)`	`O(n²)`

Common pitfalls

Starting the search below grid[0][0] or grid[n-1][n-1].
Summing elevations (shortest path) instead of taking the max along the path.
Returning when a cell is pushed rather than when it is popped.

Interview tips

Recognise “minimise the worst step” as a minimax / bottleneck path.
Mention the monotonic predicate ⇒ binary search on the answer.
Compare with Path With Minimum Effort — same Dijkstra template.

Pattern

Minimax path / Dijkstra with max → minimise the largest weight seen along a path in a grid or graph.

My notes saved in this browser