How do you solve Swim in Rising Water?

Initialize a min-heap with the starting cell and its elevation. Maintain a visited set to avoid revisiting cells. Repeatedly pop the cell with the lowest elevation from the heap, update the current maximum elevation along the path, and push all unvisited neighbors into the heap with their elevations. When the destination cell is popped, return the maximum elevation encountered, which corresponds to the minimum time needed to swim across.

What pattern does Swim in Rising Water use?

The Pattern: Heap / Priority Queue (Best-First Search on Grid) The Heuristic: When a problem requires minimizing the maximum cost along a path in a grid or graph, use a priority queue to always expand the next node with the lowest cost, ensuring the first time the target is reached corresponds to the optimal path.

Swim in Rising Water — Heap / Priority Queue

Q: What is the time complexity of Swim in Rising Water?

O(N^2 log N). Each cell is pushed and popped from the min-heap at most once. The heap operations take O(log (N^2)) = O(2 log N) = O(log N) time. Since there are N^2 cells, total complexity is O(N^2 log N).

Problem

Given an N x N grid of integers representing elevation heights, return the minimum time required to swim from the top-left corner to the bottom-right corner, where you can only swim to adjacent squares with elevation less than or equal to the current time.

2 ≤ N ≤ 50
grid.length == N
grid[i].length == N
0 ≤ grid[i][j] < N*N
All values in grid are unique

Example

Input: grid = [[0,2],[1,3]]

Output: 3

At time 0, you can only stand on grid[0][0] with elevation 0. You cannot move to grid[0][1] or grid[1][0] because their elevations (2 and 1) are higher than 0. As time increases, the water level rises. At time 1, you can move to grid[1][0] (elevation 1). At time 2, grid[0][1] becomes accessible. Finally, at time 3, grid[1][1] is accessible, allowing you to reach the bottom-right corner. The minimum time to reach the destination is 3.

Approach

Straightforward Solution

A brute-force approach would try all paths from start to end, tracking the maximum elevation on each path, which is exponential and infeasible for larger grids.

Core Observation

The minimum time to reach the destination is governed by the highest elevation encountered along any path from start to end. This means the problem reduces to finding a path minimizing the maximum elevation on that path.

Path to Optimal

Preview

Recognizing that the problem is to minimize the maximum elevation along a path suggests using a best-first search approach…

Full step-by-step walkthrough on Pro →

Optimal Approach

Preview

Initialize a min-heap with the starting cell and its elevation. Maintain a visited set to avoid revisiting cells…

Full step-by-step walkthrough on Pro →

Want the full reasoning chain?

Unlock the complete walkthrough, line-by-line analysis, and recall drill.

Unlock Pro

Time

O(N^2 log N)

Each cell is pushed and popped from the min-heap at most once. The heap operations take O(log (N^2)) = O(2 log N) = O(log N) time. Since there are N^2 cells, total complexity is O(N^2 log N).

Space

O(N^2)

The visited set and min-heap can each hold up to all N^2 cells in the worst case, resulting in O(N^2) auxiliary space.

Solution

Python

1import heapq
2
3class Solution:
  def swimInWater(self, grid: list[list[int]]) -> int:
      N = len(grid)
      visit = set()
      min_heap = [[grid[0][0], 0, 0]]
      directions = [[0, 1], [0, -1], [1, 0], [-1, 0]]
      visit.add((0, 0))
10
      while min_heap:
          t, r, c = heapq.heappop(min_heap)
13
          if r == N - 1 and c == N - 1:
              return t
          
          for dr, dc in directions:
              nei_r, nei_c = r + dr, c + dc
              if (nei_r < 0 or nei_c < 0 or
                  nei_r == N or nei_c == N or
                  (nei_r, nei_c) in visit):
                  continue
              
              visit.add((nei_r, nei_c))
              new_time = max(t, grid[nei_r][nei_c])
              heapq.heappush(min_heap, [new_time, nei_r, nei_c])

Step-by-Step Solution

1

Initialize Grid Size, Visited Set, and Min-Heap with Starting Cell

5N = len(grid)
6visit = set()
7min_heap = [[grid[0][0], 0, 0]]
8directions = [[0, 1], [0, -1], [1, 0], [-1, 0]]
9visit.add((0, 0))

Objective

To set up the initial state for the best-first search, including grid dimensions, tracking visited cells, and the priority queue seeded with the starting position.

Key Insight

Starting with the top-left cell in the min-heap keyed by its elevation allows the algorithm to begin exploring from the lowest elevation point. The visited set prevents revisiting cells, ensuring efficiency and correctness by avoiding cycles and redundant work.

Interview Quick-Check

Core Logic

The min-heap stores cells prioritized by their elevation, enabling the algorithm to always explore the next lowest elevation cell.

State & Boundaries

The visited set ensures each cell is processed only once, preventing infinite loops and redundant heap insertions.

Common Pitfalls & Bugs

Forgetting to add the starting cell to the visited set can cause it to be processed multiple times.

2

Expand Reachable Cells by Popping Lowest Elevation and Adding Neighbors

To iteratively explore the grid by always moving to the adjacent cell with the lowest elevation not yet visited, updating the maximum elevation along the path.

1 more step with full analysis available on Pro.

Line Analysis

This solution has 6 Critical lines interviewers watch for.

Line 12 Critical

t, r, c = heapq.heappop(min_heap)

Pop the cell with the lowest elevation from the min-heap.

This operation selects the next cell to explore with the minimal elevation, which is critical to the best-first search strategy that guarantees minimal maximum elevation path.

Line 7 Critical

min_heap = [[grid[0][0], 0, 0]]

Initialize a min-heap with the starting cell's elevation and coordinates.

The min-heap prioritizes exploration by elevation, enabling the algorithm to always expand the lowest elevation cell next, which is essential for finding the minimal maximum elevation path.

Line 14 Critical

if r == N - 1 and c == N - 1:

Check if the current cell is the destination.

Detecting the destination allows immediate termination, as the first time it is popped corresponds to the minimal maximum elevation path.

Full line-by-line criticality + rationale for all 18 lines available on Pro.

Test Your Understanding

Why does popping the destination cell from the min-heap guarantee that the path found has the minimal maximum elevation?

See the answer with Pro.

Don't just read it. Drill it.

Reconstruct Swim in Rising Water from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.

Unlock the Swim in Rising Water drill

or drill a free problem

1	`import heapq`
2
3	`class Solution:`
4	`def swimInWater(self, grid: list[list[int]]) -> int:`
5	`N = len(grid)`
6	`visit = set()`
7	`min_heap = [[grid[0][0], 0, 0]]`
8	`directions = [[0, 1], [0, -1], [1, 0], [-1, 0]]`
9	`visit.add((0, 0))`
10
11	`while min_heap:`
12	`t, r, c = heapq.heappop(min_heap)`
13
14	`if r == N - 1 and c == N - 1:`
15	`return t`
16
17	`for dr, dc in directions:`
18	`nei_r, nei_c = r + dr, c + dc`
19	`if (nei_r < 0 or nei_c < 0 or`
20	`nei_r == N or nei_c == N or`
21	`(nei_r, nei_c) in visit):`
22	`continue`
23
24	`visit.add((nei_r, nei_c))`
25	`new_time = max(t, grid[nei_r][nei_c])`
26	`heapq.heappush(min_heap, [new_time, nei_r, nei_c])`

5	`N = len(grid)`
6	`visit = set()`
7	`min_heap = [[grid[0][0], 0, 0]]`
8	`directions = [[0, 1], [0, -1], [1, 0], [-1, 0]]`
9	`visit.add((0, 0))`