Loading problems...
TL;DR: We apply a modified Dijkstra's algorithm to find a path from the top-left to the bottom-right of the grid that minimizes the maximum elevation encountered along the route.
The problem asks for the minimum time required to travel from coordinates to in an grid. At any time , you can only traverse cells with an elevation value less than or equal to . This implies that the "cost" of a path is determined by the single cell with the highest elevation on that path. We must find a path such that this maximum value is minimized. This is a classic "bottleneck path" problem, making it a popular interview question for testing graph traversal knowledge.
A naive approach to solving LeetCode 778 involves checking every possible time to see if a path exists. Since the grid values are bounded between and , we can iterate through each potential water level and perform a traversal.
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 , where is the range of possible elevation values () and the traversal takes . This results in . While the constraint 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 .
The key intuition for the optimal solution lies in recognizing this as a shortest path problem on a weighted graph. Each cell 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 , we have done so via the path with the lowest possible maximum elevation.
Visual Description: Imagine the grid as a topography. We start at . 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.

Setup:
pq.visited array of size , initialized to false.(grid[0][0], 0, 0) to pq.(0, 0) as visited.Processing Loop:
pq is not empty:
(t, r, c).r == n - 1 and c == n - 1, return t.(nr, nc).(nr, nc) is within grid bounds and not visited:
new_t = max(t, grid[nr][nc]).(nr, nc) as visited.(new_t, nr, nc) to pq.Result: The loop is guaranteed to return the result because a path always exists on a connected grid.
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.
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 } };
javaimport 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 } }
pythonimport 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
Time Complexity:
Space Complexity:
visited array.The logic used in the Swim in Rising Water Solution applies directly to several other "bottleneck" and shortest-path variations:
Why does a standard BFS/DFS approach fail? Standard BFS finds the path with the fewest number of edges (steps). In this problem, a path with 50 steps might be better than a path with 2 steps if the 50-step path has lower elevation values. Ignoring the weights (elevations) leads to incorrect answers.
Why is my solution getting Time Limit Exceeded (TLE)?
This usually happens if you do not mark nodes as visited immediately upon pushing them to the Priority Queue (or upon popping, if handled carefully). In Dijkstra, strictly speaking, a node is "settled" when popped. However, in grid problems, adding the same node to the PQ multiple times can cause the queue to grow exponentially. Ensuring a node is added to the PQ/visited set only once (or updating its priority) is crucial for performance.
Why is the answer sometimes wrong on test cases?
A common logic error is calculating the cost as current_time + grid[nr][nc]. This calculates the sum of elevations. The problem asks for the maximum elevation encountered. The correct transition logic is max(current_time, grid[nr][nc]).