Swim in Rising Water

hardAdvanced Graphs (Dijkstra / MST)372 stepsJava · Python · C++

At time t you can swim through cells with height ≤ t. Find the earliest time to reach the bottom-right. The answer is the smallest possible maximum height along a path, so expand cells in order of height with a min-heap, tracking the highest cell seen.

▶ Watch the animated trace

Traced 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]] → 16. Original problem: neetcode.io/problems/swim-in-rising-water

Complexity

BestO(n² log n)

AverageO(n² log n)

WorstO(n² log n)

SpaceO(n²)

Each cell is pushed once.

Key idea

A path is usable at time t exactly when its highest cell is ≤ t.
Always expand the lowest reachable cell next (min-heap by height).
The time needed so far is the largest height popped.
Stop when the target is popped.

Common mistakes

BFS by steps ignores heights.
Forgetting that the start cell's own height counts.

Solution

Java

// DIRS = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}}: down, up, right, left
int swimInWater(int[][] grid) {
    int n = grid.length, time = 0;
    boolean[][] seen = new boolean[n][n];
    PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> Integer.compare(a[0], b[0]));
    pq.offer(new int[]{grid[0][0], 0, 0});
    seen[0][0] = true;
    while (!pq.isEmpty()) {
        int[] top = pq.poll();
        time = Math.max(time, top[0]);
        int r = top[1], c = top[2];
        if (r == n - 1 && c == n - 1) return time;
        for (int[] d : DIRS) {
            int nr = r + d[0], nc = c + d[1];
            if (nr < 0 || nc < 0 || nr >= n || nc >= n || seen[nr][nc]) continue;
            seen[nr][nc] = true;
            pq.offer(new int[]{grid[nr][nc], nr, nc});
        }
    }
    return time;
}

Python

# DIRS = [(1, 0), (-1, 0), (0, 1), (0, -1)]: down, up, right, left
def swimInWater(grid: List[List[int]]) -> int:
    n, time = len(grid), 0
    seen = {(0, 0)}
    heap = [(grid[0][0], 0, 0)]
    while heap:
        h, r, c = heapq.heappop(heap)
        time = max(time, h)
        if r == n - 1 and c == n - 1: return time
        for dr, dc in DIRS:
            nr, nc = r + dr, c + dc
            if 0 <= nr < n and 0 <= nc < n and (nr, nc) not in seen:
                seen.add((nr, nc))
                heapq.heappush(heap, (grid[nr][nc], nr, nc))
    return time

C++

// DIRS = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}}: down, up, right, left
int swimInWater(vector<vector<int>>& grid) {
    int n = grid.size(), time = 0;
    vector<vector<bool>> seen(n, vector<bool>(n));
    priority_queue<array<int, 3>, vector<array<int, 3>>, greater<>> pq;
    pq.push({grid[0][0], 0, 0});
    seen[0][0] = true;
    while (!pq.empty()) {
        auto [h, r, c] = pq.top(); pq.pop();
        time = max(time, h);
        if (r == n - 1 && c == n - 1) return time;
        for (auto& d : DIRS) {
            int nr = r + d[0], nc = c + d[1];
            if (nr < 0 || nc < 0 || nr >= n || nc >= n || seen[nr][nc]) continue;
            seen[nr][nc] = true;
            pq.push({grid[nr][nc], nr, nc});
        }
    }
    return time;
}

Edge cases

Each one has its own trace in the interactive view.

Case	Input	Answer
2×2 grid The target itself is height 3.	`grid = [[0, 2], [1, 3]]`	`3`
Single cell Already there.	`grid = [[0]]`	`0`
High start You can't leave until the water covers the start.	`grid = [[3, 0], [1, 2]]`	`3`