Swim in Rising Water

PracticeNeetCode ↗LeetCode ↗

Given an n×n grid where grid[i][j] is a cell's elevation, water rises over time. At time t you may swim between adjacent cells only if both have elevation ≤ t. Starting at (0,0), return the minimum time needed to reach (n-1, n-1).

Example

Key Pointers

• The answer is the minimum possible value of "the highest elevation encountered along some path" — not a sum of elevations.
• A min-heap keyed by elevation lets you always expand the currently-easiest cell to reach next — the same greedy idea Dijkstra uses for shortest paths, but tracking a running max instead of a running sum.
• The first time the bottom-right cell is popped off the heap, its recorded time is guaranteed minimal — no need to check any other path.

Step-by-Step Analysis

1. Push (grid[0][0], 0, 0) onto a min-heap and mark (0,0) visited.
2. Pop the cell with the smallest recorded time; if it's the bottom-right cell, that time is the answer.
3. For each of its unvisited 4-directional neighbors, compute the time to reach it as max(current time, that neighbor's elevation), mark it visited, and push it.
4. Repeat until the destination is popped off the heap.

Complexity

Time: O(n² log n) — Space: O(n²)

Code

import heapq

def swimInWater(grid: list[list[int]]) -> int:
    n = len(grid)
    visited = [[False] * n for _ in range(n)]
    min_heap = [(grid[0][0], 0, 0)]
    visited[0][0] = True
    directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]

    while min_heap:
        time, r, c = heapq.heappop(min_heap)
        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 not visited[nr][nc]:
                visited[nr][nc] = True
                heapq.heappush(min_heap, (max(time, grid[nr][nc]), nr, nc))

    return -1

Code Explanation

How the solution above works, piece by piece.

1. You can swim along a path once the water is at least as high as every cell on it, so a path costs its maximum elevation.
2. The heap holds (time, r, c): the minimal max-elevation needed to reach that cell so far.
3. Pop the cell with the lowest time. If it's the bottom-right corner, that time is the answer.
4. Push each unvisited neighbour with max(time, grid[nr][nc]): the path's max grows only if the new cell is higher.
5. It's Dijkstra with "max" instead of "+": O(n² log n).

Visual Walkthrough

Running it on grid = [[0, 2], [1, 3]]:

Video Explanation

NeetCode — Dijkstra's Algorithm, LeetCode 778