Brute Force Approach for Swim in Rising Water

A naive approach to solving LeetCode 778 involves checking every possible time $t$ to see if a path exists. Since the grid values are bounded between $0$ and $n^2 - 1$, we can iterate through each potential water level and perform a traversal.

1. Iterate $t$ from $0$ to $n^2$.
2. For each $t$, run a Breadth-First Search (BFS) or Depth-First Search (DFS) starting at $(0,0)$.
3. During traversal, only move to adjacent cells if their elevation is $\le t$.
4. The first $t$ for which the traversal reaches $(n-1, n-1)$ is the answer.

python
# Pseudo-code for Brute Force
for t in range(n * n):
    if can_reach_end(t, grid):
        return t

Complexity Analysis: The time complexity is $O(T \times N^2)$, where $T$ is the range of possible elevation values ($N^2$) and the traversal takes $O(N^2)$. This results in $O(N^4)$. While the constraint $N \le 50$ makes this theoretically passable, it is highly inefficient compared to the optimal solution. The approach fails to utilize the greedy property of the graph structure, performing redundant work by re-scanning the grid for every increment of $t$.

Core Insight for Swim in Rising Water

The key intuition for the optimal solution lies in recognizing this as a shortest path problem on a weighted graph. Each cell $(r, c)$ is a node, and edges connect adjacent cells. The weight of an edge entering a node is the elevation of that node.

However, unlike standard shortest path problems where we minimize the sum of weights (distance), here we minimize the maximum weight encountered (bottleneck).

The invariant enforced by Dijkstra's algorithm is that when we extract a node from the Priority Queue (PQ), we have found the optimal (minimal) cost to reach that node. By prioritizing the exploration of nodes with the lowest required water level, we ensure that the first time we reach the target $(n-1, n-1)$, we have done so via the path with the lowest possible maximum elevation.

Visual Description: Imagine the grid as a topography. We start at $(0,0)$. We maintain a "frontier" of reachable nodes in a Priority Queue. At each step, we expand the frontier by choosing the node with the lowest elevation (or lowest required water level to reach it). This effectively "floods" the grid from the start point, always spilling over into the lowest available adjacent terrain first. The algorithm visualizes a wave expanding strictly through the path of least resistance until it touches the destination.

Execution Flow

1. Setup:

   • Create a Min-Heap pq.
   • Create a visited array of size $N \times N$, initialized to false.
   • Add (grid[0][0], 0, 0) to pq.
   • Mark (0, 0) as visited.

2. Processing Loop:

   • While pq is not empty:
     • Pop the element with the smallest time: (t, r, c).
     • Check Target: If r == n - 1 and c == n - 1, return t.
     • Expand Neighbors: For each direction (up, down, left, right):
       • Calculate neighbor coordinates (nr, nc).
       • Check boundaries: If (nr, nc) is within grid bounds and not visited:
         • Calculate new time: new_t = max(t, grid[nr][nc]).
         • Mark (nr, nc) as visited.
         • Push (new_t, nr, nc) to pq.

3. Result: The loop is guaranteed to return the result because a path always exists on a connected grid.

Proof of Correctness

Dijkstra's algorithm guarantees correctness for this problem because the cost function is monotonically non-decreasing. The cost to reach a neighbor is max(current_path_max, neighbor_elevation). This value can never be less than current_path_max.

Because we always expand the node with the absolute minimum bottleneck value currently reachable, the first time we pop the destination node from the priority queue, we are guaranteed that no other path exists with a smaller bottleneck. Any other path currently in the queue already has a starting bottleneck equal to or greater than the one we just processed.

Reference Implementation

C++ Solution for LeetCode 778

cpp
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

class Solution {
public:
    int swimInWater(vector<vector<int>>& grid) {
        int n = grid.size();
        // Min-heap stores {time, r, c}
        // Orders by time ascending
        priority_queue<vector<int>, vector<vector<int>>, greater<vector<int>>> pq;
        
        // Visited array to prevent cycles
        vector<vector<bool>> visited(n, vector<bool>(n, false));
        
        // Start at (0,0). Initial time is the elevation of the start.
        pq.push({grid[0][0], 0, 0});
        visited[0][0] = true;
        
        int dr[] = {-1, 1, 0, 0};
        int dc[] = {0, 0, -1, 1};
        
        while (!pq.empty()) {
            auto curr = pq.top();
            pq.pop();
            
            int time = curr[0];
            int r = curr[1];
            int c = curr[2];
            
            // If we reached the bottom-right, return the time
            if (r == n - 1 && c == n - 1) {
                return time;
            }
            
            for (int i = 0; i < 4; i++) {
                int nr = r + dr[i];
                int nc = c + dc[i];
                
                if (nr >= 0 && nr < n && nc >= 0 && nc < n && !visited[nr][nc]) {
                    visited[nr][nc] = true;
                    // The time to reach the neighbor is max of current path time 
                    // and the neighbor's elevation
                    int newTime = max(time, grid[nr][nc]);
                    pq.push({newTime, nr, nc});
                }
            }
        }
        
        return -1; // Should not reach here
    }
};

Java Solution for LeetCode 778

java
import java.util.PriorityQueue;

class Solution {
    public int swimInWater(int[][] grid) {
        int n = grid.length;
        // PriorityQueue stores int[] {time, r, c}
        // Ordered by time ascending
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[0] - b[0]);
        
        boolean[][] visited = new boolean[n][n];
        
        // Initial state
        pq.offer(new int[]{grid[0][0], 0, 0});
        visited[0][0] = true;
        
        int[][] directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
        
        while (!pq.isEmpty()) {
            int[] curr = pq.poll();
            int time = curr[0];
            int r = curr[1];
            int c = curr[2];
            
            // Target reached
            if (r == n - 1 && c == n - 1) {
                return time;
            }
            
            for (int[] dir : directions) {
                int nr = r + dir[0];
                int nc = c + dir[1];
                
                if (nr >= 0 && nr < n && nc >= 0 && nc < n && !visited[nr][nc]) {
                    visited[nr][nc] = true;
                    // Calculate bottleneck cost
                    int newTime = Math.max(time, grid[nr][nc]);
                    pq.offer(new int[]{newTime, nr, nc});
                }
            }
        }
        
        return -1; // Should not be reached
    }
}

Python Solution for LeetCode 778

python
import heapq

class Solution:
    def swimInWater(self, grid: list[list[int]]) -> int:
        n = len(grid)
        # Min-heap stores (time, r, c)
        pq = [(grid[0][0], 0, 0)]
        
        visited = set()
        visited.add((0, 0))
        
        directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
        
        while pq:
            time, r, c = heapq.heappop(pq)
            
            if r == n - 1 and c == n - 1:
                return time
            
            for dr, dc in directions:
                nr, nc = r + dr, c + dc
                
                if 0 <= nr < n and 0 <= nc < n and (nr, nc) not in visited:
                    visited.add((nr, nc))
                    # The new time is the bottleneck: max of current path and cell height
                    new_time = max(time, grid[nr][nc])
                    heapq.heappush(pq, (new_time, nr, nc))
                    
        return -1