Swim in Rising Water: Binary Search Meets Graph Traversal

LeetCode 778: Swim in Rising Water gives you an n x n grid where grid[i][j] represents the elevation at cell (i, j). At time t, every cell with elevation at most t is underwater. You start at (0, 0) and need to reach (n-1, n-1). At any time t, you can swim to any adjacent cell (up, down, left, right) as long as both your current cell and the destination cell are underwater. Find the minimum time t such that there exists a path from the top-left corner to the bottom-right corner.

Think of it this way: the water level rises over time. At time t = 0, only cells with elevation 0 are submerged. At t = 3, all cells with elevation 0, 1, 2, or 3 are underwater. You need to find the earliest moment when a continuous underwater path connects the start to the goal.

Why this problem matters

Swim in Rising Water is one of those problems that looks like a graph search at first glance, and it is, but the real trick is recognizing that you can frame the question differently. Instead of asking "what is the shortest path?", you ask "what is the minimum threshold that makes a path possible?" That reframing opens the door to two elegant approaches: binary search on the answer with BFS, and a modified Dijkstra's algorithm with a min-heap.

This problem sits at the intersection of three fundamental patterns: graph traversal on a grid, binary search on the answer space, and shortest-path algorithms with heaps. If you are preparing for interviews, solving this one problem exercises all three muscles at once. You will see these same building blocks in problems like Koko Eating Bananas (binary search on answer), Number of Islands (grid BFS), and Network Delay Time (Dijkstra's).

The constraint that makes this problem interesting is that you are not minimizing the total cost of a path. You are minimizing the bottleneck, the single highest elevation along the path. That subtle difference is why Dijkstra's variant works here and why the binary search approach fits so naturally.

Approach 1: Binary search + BFS

The key insight is that the answer t is monotonic. If you can swim from (0,0) to (n-1,n-1) at time t, you can certainly do it at time t + 1 (more cells are underwater). If you cannot do it at time t, you definitely cannot do it at time t - 1 (fewer cells available). This monotonic property means we can binary search on t.

For each candidate time mid, run a BFS or DFS starting from (0,0). Only visit cells where grid[r][c] is at most mid. If you can reach (n-1, n-1), then mid is feasible, and maybe something smaller works too. If you cannot reach it, you need a larger t.

The search range is lo = max(grid[0][0], grid[n-1][n-1]) (you need at least both endpoints to be submerged) up to hi = n*n - 1 (the maximum possible elevation, since the grid is a permutation of values 0 through n*n - 1).

from collections import deque

def swim_in_water(grid: list[list[int]]) -> int:
    n = len(grid)

    def can_reach(t: int) -> bool:
        if grid[0][0] > t or grid[n - 1][n - 1] > t:
            return False
        visited = [[False] * n for _ in range(n)]
        visited[0][0] = True
        queue = deque([(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 not visited[nr][nc] and grid[nr][nc] <= t:
                    visited[nr][nc] = True
                    queue.append((nr, nc))
        return False

    lo = max(grid[0][0], grid[n - 1][n - 1])
    hi = n * n - 1

    while lo < hi:
        mid = lo + (hi - lo) // 2
        if can_reach(mid):
            hi = mid
        else:
            lo = mid + 1

    return lo

Step-by-step walkthrough

Let's trace the binary search + BFS approach on a 3x3 grid with elevations [[0,1,2],[5,4,3],[6,8,7]]. The grid contains values 0 through 8. The optimal path goes (0,0) -> (0,1) -> (0,2) -> (1,2) -> (2,2) with max elevation 7, so the answer is t = 7.

Four steps. The binary search quickly narrows down from the full range [0, 8] to the exact answer t = 7. Each step runs a BFS that takes O(n^2) time, and we do O(log(n^2)) = O(log n) iterations.

Approach 2: Modified Dijkstra with min-heap

Instead of binary searching on the answer, you can solve this directly with a modified Dijkstra's algorithm. The idea: treat each cell as a node and use a min-heap to always expand the cell with the smallest "cost so far", where the cost to reach a cell is the maximum elevation along the path to that cell.

Start at (0,0) with cost grid[0][0]. For each neighbor, the cost to reach it through the current cell is max(current_cost, grid[nr][nc]). Push that into the heap. When you pop (n-1, n-1) from the heap, you have found the minimum bottleneck path.

This works because the heap ensures you always process the path with the smallest bottleneck first. Once you pop a cell, its optimal cost is finalized, just like standard Dijkstra's.

import heapq

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

    while heap:
        cost, r, c = heapq.heappop(heap)
        if r == n - 1 and c == n - 1:
            return cost
        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 not visited[nr][nc]:
                visited[nr][nc] = True
                heapq.heappush(heap, (max(cost, grid[nr][nc]), nr, nc))

    return -1  # unreachable (should not happen with valid input)

The Dijkstra approach is often cleaner to implement and avoids writing the separate can_reach function. Both approaches yield the same asymptotic complexity, but the heap version tends to do less total work in practice because it finds the answer in a single pass rather than running multiple BFS traversals.

Complexity analysis

Binary search + BFS: The binary search runs O(log(n^2)) = O(log n) iterations. Each BFS visits at most n^2 cells. Total: O(n^2 log n). Space is O(n^2) for the visited grid.

Min-heap (Dijkstra): Each of the n^2 cells is pushed onto the heap at most once. Each push/pop costs O(log(n^2)) = O(log n). Total: O(n^2 log n). Space is O(n^2) for the heap and visited grid.

Edge cases to watch for

• 1x1 grid: The start is the goal. Return grid[0][0] immediately.
• Start or goal has the highest elevation: If grid[0][0] or grid[n-1][n-1] is the max value, the answer is at least that value. Both approaches handle this naturally.
• Direct path along the top and right edges: This is a common optimal path shape. Make sure your BFS explores all four directions.
• The grid is a permutation: The problem guarantees all values are distinct and range from 0 to n*n - 1. This means the binary search range is well defined and bounded.

The building blocks

This problem combines two core building blocks.

Binary search on the answer: You are not searching an array for a target. You are searching the range of possible answer values and using a feasibility check (BFS reachability) to decide which half to keep. This is the same pattern as Koko Eating Bananas and Capacity to Ship Packages Within D Days.

Graph traversal on a grid: The BFS/DFS on a 2D grid with four-directional movement is the same traversal you use in Number of Islands, Flood Fill, and Surrounded Regions. The only twist is the elevation threshold that determines which cells are passable.

Min-heap shortest path (Dijkstra variant): Instead of minimizing total distance, you minimize the maximum edge weight along the path. This "minimax path" variant of Dijkstra shows up whenever the cost metric is a bottleneck rather than a sum. The heap guarantees you process paths in order of their bottleneck cost.

From understanding to recall

You understand the two approaches now. Binary search picks a water level, BFS checks if a path exists, and the search converges. The Dijkstra variant greedily expands the lowest-cost frontier using a heap. Both are clean and elegant.

But writing either one from scratch under interview pressure is a different story. Did the BFS check grid[nr][nc] <= t or grid[nr][nc] < t? Does the Dijkstra version mark visited on push or on pop? Is the binary search bound n*n - 1 or n*n? These details matter, and they are exactly the kind of thing that fades from memory after a few weeks. Spaced repetition locks them in. You write the solution today, again in two days, again in a week. After a few rounds, the grid BFS template and the heap loop are second nature.

Related posts

• Koko Eating Bananas - Another binary search on the answer problem
• Number of Islands - Grid BFS/DFS traversal
• Network Delay Time - Dijkstra's algorithm on graphs