Swim in Rising Water

Difficulty: Hard Source: NeetCode

Problem

You are given an n x n integer matrix grid where each value grid[i][j] represents the elevation at position (i, j).

The rain starts to fall. At time t, the depth of the water everywhere is t. You can swim from a square to another 4-directionally adjacent square if and only if the elevation of both squares individually is at most t. You can swim infinite distances in zero time. Of course, you must stay within the boundaries of the grid during your swim.

Return the least time until you can reach the bottom right square (n - 1, n - 1) if you start at the top left square (0, 0).

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

Example 2: Input: grid = [[0,1,2,3,4],[24,23,22,21,5],[12,13,14,15,16],[11,17,18,19,20],[10,9,8,7,6]] Output: 16

Constraints:

• n == grid.length
• n == grid[i].length
• 1 <= n <= 50
• 0 <= grid[i][j] < n^2
• Each value grid[i][j] is unique

Prerequisites

Before attempting this problem, you should be comfortable with:

• Dijkstra’s Algorithm — shortest path in a weighted graph
• Binary Search on Answer — searching for the optimal time value
• BFS/DFS — for checking connectivity at a given time

1. Binary Search + BFS

Intuition

Binary search on the answer: for a given time t, can we reach the bottom-right corner? A cell (r, c) is reachable at time t if grid[r][c] <= t. We need both the source and every cell along the path to have elevation <= t. Binary search over t from 0 to n*n - 1, and use BFS to check feasibility at each candidate.

Algorithm

1. Binary search: lo = grid[0][0], hi = n*n - 1.
2. For each mid, run BFS from (0, 0) visiting only cells with value <= mid.
3. If (n-1, n-1) is reachable, shrink to hi = mid. Else lo = mid + 1.
4. Return lo.

Solution

from collections import deque

def swimInWater_binary(grid):
    n = len(grid)

    def can_reach(t):
        if grid[0][0] > t:
            return False
        queue = deque([(0, 0)])
        visited = {(0, 0)}
        while queue:
            r, c = queue.popleft()
            if r == n - 1 and c == n - 1:
                return True
            for dr, dc in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
                nr, nc = r + dr, c + dc
                if 0 <= nr < n and 0 <= nc < n and (nr, nc) not in visited and grid[nr][nc] <= t:
                    visited.add((nr, nc))
                    queue.append((nr, nc))
        return False

    lo, hi = grid[0][0], n * n - 1
    while lo < hi:
        mid = (lo + hi) // 2
        if can_reach(mid):
            hi = mid
        else:
            lo = mid + 1
    return lo


print(swimInWater_binary([[0, 2], [1, 3]]))  # 3
print(swimInWater_binary([[0, 1, 2, 3, 4], [24, 23, 22, 21, 5],
                           [12, 13, 14, 15, 16], [11, 17, 18, 19, 20],
                           [10, 9, 8, 7, 6]]))  # 16

Complexity

• Time: O(n² log n²) = O(n² log n) — binary search × BFS
• Space: O(n²) — visited set and queue

2. Dijkstra’s Algorithm

Intuition

This is a minimax path problem — we want to minimize the maximum elevation we encounter along our path (since we need to wait until time t equals the max elevation in any cell we pass through). This maps perfectly to Dijkstra: the “cost” of moving to a neighbor is max(current_cost, grid[nr][nc]). We always expand the cell with the smallest current max elevation.

The answer is the cost to reach (n-1, n-1).

Algorithm

1. Initialize dist[0][0] = grid[0][0], all others to infinity.
2. Push (grid[0][0], 0, 0) into the min-heap.
3. While heap is not empty:
   • Pop (cost, r, c).
   • If (r, c) is the destination, return cost.
   • Skip if cost > dist[r][c] (stale).
   • For each neighbor, compute new_cost = max(cost, grid[nr][nc]).
   • If new_cost < dist[nr][nc], update and push.
4. Return dist[n-1][n-1].

Solution

import heapq

def swimInWater(grid):
    n = len(grid)
    dist = [[float('inf')] * n for _ in range(n)]
    dist[0][0] = grid[0][0]
    heap = [(grid[0][0], 0, 0)]  # (max_elevation, row, col)

    while heap:
        cost, r, c = heapq.heappop(heap)

        if r == n - 1 and c == n - 1:
            return cost

        if cost > dist[r][c]:
            continue

        for dr, dc in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
            nr, nc = r + dr, c + dc
            if 0 <= nr < n and 0 <= nc < n:
                new_cost = max(cost, grid[nr][nc])
                if new_cost < dist[nr][nc]:
                    dist[nr][nc] = new_cost
                    heapq.heappush(heap, (new_cost, nr, nc))

    return dist[n - 1][n - 1]


print(swimInWater([[0, 2], [1, 3]]))  # 3
print(swimInWater([[0, 1, 2, 3, 4], [24, 23, 22, 21, 5],
                   [12, 13, 14, 15, 16], [11, 17, 18, 19, 20],
                   [10, 9, 8, 7, 6]]))  # 16
print(swimInWater([[0]]))              # 0

Complexity

• Time: O(n² log n²) = O(n² log n) — each cell pushed/popped from heap at most once
• Space: O(n²) — dist grid and heap

Common Pitfalls

Confusing this with total-sum Dijkstra. The “cost” here is the maximum elevation seen so far, not the sum. Use max(cost, grid[nr][nc]) not addition.

Starting cost should be grid[0][0], not 0. You’re standing on cell (0, 0), so you need to wait until time grid[0][0] just to start. Initialize the heap with grid[0][0].

Checking destination mid-loop vs at the end. Both work, but checking when you pop from the heap (as done above) is slightly cleaner and can exit earlier.