LeetCode · #778

Swim in Rising Water Solution

You can enter a cell only once the water level reaches that cell's elevation. Return the earliest time when a path from the top-left to the bottom-right becomes possible.

Section One · Problem

Problem Statement

🏷️

Difficulty

Medium

🔗

LeetCode

Problem #778

🏗️

Pattern

Dijkstra minimax path

If a path visits cells with elevations [0, 2, 5, 4], then you must wait until time 5 before the entire path is swimmable. So the cost of a path is the maximum elevation on it.

Example

Input:  grid = [[0,2],[1,3]]
Output: 3
// You must wait until time 3 to enter the destination cell.

Section Two · Approach 1

Try All Grid Paths — Exponential

A brute-force DFS can enumerate all possible routes, track the maximum elevation used on each path, and keep the minimum among them.

Why it works

The earliest feasible time is exactly the smallest possible maximum elevation over all source-to-target paths.

Problem: There are far too many paths. Once we already know a way to reach a cell with threshold t, any new route reaching that same cell with threshold ≥ t is dominated and can be ignored. Dijkstra captures that dominance naturally.

Section Three · Approach 2

Grid Dijkstra with Max Elevation State — O(n² log n)

Use a min-heap storing the current minimum known threshold to reach each cell. If you move into neighbor (nr,nc), the threshold becomes max(currentTime, grid[nr][nc]). This is the same minimax Dijkstra pattern as LC 1631, but the edge cost is simply the destination cell's elevation.

💡 Mental model: Water level rises globally over time. Dijkstra asks: what is the earliest time each frontier cell could possibly become reachable if we choose the best route so far? We always expand the currently most promising reachable cell first.

Start time is already at least grid[0][0].
Maintain best[r][c] = smallest threshold found so far for that cell.
Pop the smallest threshold from the heap.
Relax neighbors with next = max(current, grid[nr][nc]).
The first time the destination is popped, its threshold is final.

Alternative view:

This can also be solved with binary search on time plus BFS feasibility.
Dijkstra is often simpler because it avoids a second search layer and directly constructs the answer.

Section Four · Trace

Visual Walkthrough

Trace [[0,2],[1,3]].

Swim in Rising Water — Dijkstra threshold expansion

Section Five · Implementation

Code — Java & Python

Java — Dijkstra threshold search

import java.util.*;

class Solution {
    private static final int[][] DIRS = {{1,0}, {-1,0}, {0,1}, {0,-1}};

    public int swimInWater(int[][] grid) {
        int n = grid.length;
        int[][] best = new int[n][n];
        for (int[] row : best) Arrays.fill(row, Integer.MAX_VALUE);
        best[0][0] = grid[0][0];

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

        while (!pq.isEmpty()) {
            int[] cur = pq.poll();
            int time = cur[0], r = cur[1], c = cur[2];
            if (time != best[r][c]) continue;
            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 || nr >= n || nc < 0 || nc >= n) continue;
                int nextTime = Math.max(time, grid[nr][nc]);
                if (nextTime < best[nr][nc]) {
                    best[nr][nc] = nextTime;
                    pq.offer(new int[] { nextTime, nr, nc });
                }
            }
        }

        return -1;
    }
}

Python — minimax grid path

import heapq

class Solution:
    def swimInWater(self, grid: list[list[int]]) -> int:
        n = len(grid)
        best = [[float('inf')] * n for _ in range(n)]
        best[0][0] = grid[0][0]
        heap = [(grid[0][0], 0, 0)]
        dirs = [(1, 0), (-1, 0), (0, 1), (0, -1)]

        while heap:
            time, r, c = heapq.heappop(heap)
            if time != best[r][c]:
                continue
            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:
                    next_time = max(time, grid[nr][nc])
                    if next_time < best[nr][nc]:
                        best[nr][nc] = next_time
                        heapq.heappush(heap, (next_time, nr, nc))

        return -1

Section Six · Analysis

Complexity Analysis

Approach	Time	Space	Trade-off
DFS over all routes	Exponential	O(n²) recursion	Too many possible paths.
Dijkstra ← optimal	O(n² log n)	O(n²)	Each cell tracks the earliest global water level needed to reach it.

Section Seven · Edge Cases

Edge Cases & Pitfalls

Case	Expected behavior	Why it matters
Single cell grid	Return its elevation	You start there, so must wait for that cell to be swimmable.
Destination has highest value	Answer is at least that value	You cannot enter the end cell before its elevation is underwater.
Route with low sum but one huge peak	May be worse	Objective is maximum elevation, not sum.
Heap stale entries	Skip them	Multiple candidate thresholds per cell are normal.
Using plain BFS	Wrong answer	Cells do not all have equal traversal cost.

⚠ Common Mistake: Returning the number of steps in the path. This is not a shortest-step problem at all. The answer is the smallest water level that makes some path possible, which equals the minimum possible maximum elevation along a path.

← Back to Shortest Path

LearningTree

LC 778 · Swim in Rising Water — Solution & Explanation | DSA Guide