Generated by Codex with GPT-5

Quick facts

• Difficulty: HARD
• Problem: Swim in Rising Water
• Main tags: Array, Binary Search, Depth-First Search, Breadth-First Search, Union-Find, Heap (Priority Queue), Matrix

What the problem is really asking

The input is an n x n grid of elevations. At time t, the water level is also t, and a cell is swimmable only if its elevation is at most t.

You start in the top-left cell and want to reach the bottom-right cell. You can move up, down, left, or right, but only through cells that are already underwater enough to enter.

So the answer is not the length of the path. It is the smallest possible maximum elevation you must step on along any path from start to finish.

That is the key rephrasing:

Find a path whose highest cell is as low as possible.

Why plain BFS is not enough

If someone fixes a time t, then BFS or DFS can answer a simple yes/no question: can the swimmer reach the end using only cells with elevation <= t?

That already suggests one valid solution:

1. Binary search the answer time.
2. For each candidate time, run BFS or DFS.
3. Keep the smallest time that allows a path.

This works, but it repeats grid searches. A more direct solution lets the search itself discover the minimum time.

The key idea: Dijkstra for the worst cell on the path

Normal Dijkstra’s algorithm finds the path with the smallest sum of edge costs. This problem asks for a slightly different path cost:

the cost of a path is the maximum elevation seen on that path.

That still has the property Dijkstra needs. Once a path has already reached time t, moving to a neighbor with elevation h produces a new path cost of max(t, h). The cost never decreases as the path gets longer.

So the algorithm is:

1. Start at (0, 0) with time grid[0][0].
2. Always expand the reachable cell with the smallest known time.
3. For each neighbor, the time needed to enter it is max(current_time, neighbor_elevation).
4. When the bottom-right cell is removed from the heap, that time is optimal.

The min-heap is important because it expands paths in the order of their current best possible answer.

How to derive it in an interview

Start from the brute-force question: “Can we reach the end by time t?”

That question is monotonic. If time t works, then every larger time also works. That gives the binary-search solution and proves the answer is really a threshold.

Then improve the idea by asking: instead of guessing the threshold, can the traversal reveal cells in increasing threshold order?

Yes. Put the start cell in a min-heap ordered by the earliest time needed to reach it. Each time the algorithm pops a cell, it has found the cheapest possible way to make that cell reachable. From there, trying a neighbor only raises the time if the neighbor is higher than the current water level.

This is the same mental model as water slowly rising from the start: the heap chooses the next lowest barrier that can be crossed.

Python solution

from heapq import heappop, heappush
from math import inf
from typing import Iterable, List, Tuple


Position = Tuple[int, int]
State = Tuple[int, int, int]


class RisingWaterPathFinder:
    """Find the minimum water level needed to cross an elevation grid."""

    _DIRECTIONS: Tuple[Position, ...] = (
        (-1, 0),
        (1, 0),
        (0, -1),
        (0, 1),
    )

    def __init__(self, grid: List[List[int]]) -> None:
        self.grid = grid
        self.row_count = len(grid)
        self.column_count = len(grid[0]) if grid else 0

    def minimum_crossing_time(self) -> int:
        if self.row_count == 0 or self.column_count == 0:
            return 0

        target = (self.row_count - 1, self.column_count - 1)
        best_time = [
            [inf] * self.column_count
            for _ in range(self.row_count)
        ]

        start_time = self.grid[0][0]
        best_time[0][0] = start_time
        frontier: List[State] = [(start_time, 0, 0)]

        while frontier:
            current_time, row, col = heappop(frontier)

            if current_time != best_time[row][col]:
                continue

            if (row, col) == target:
                return current_time

            for next_row, next_col in self._neighbors(row, col):
                next_time = max(current_time, self.grid[next_row][next_col])

                if next_time >= best_time[next_row][next_col]:
                    continue

                best_time[next_row][next_col] = next_time
                heappush(frontier, (next_time, next_row, next_col))

        return -1

    def _neighbors(self, row: int, col: int) -> Iterable[Position]:
        for row_delta, col_delta in self._DIRECTIONS:
            next_row = row + row_delta
            next_col = col + col_delta

            if 0 <= next_row < self.row_count and 0 <= next_col < self.column_count:
                yield next_row, next_col


class Solution:
    def swimInWater(self, grid: List[List[int]]) -> int:
        path_finder = RisingWaterPathFinder(grid)
        return path_finder.minimum_crossing_time()

Why this works

The heap stores cells ordered by the smallest water level currently known to reach them.

When a cell is popped from the heap, every still-unprocessed path to that cell must have an equal or larger required water level. That is because the heap always chooses the lowest known level first, and moving to another cell can only keep the required level the same or raise it.

For a neighbor, the only new constraint is the neighbor’s own elevation. If the current path needs time t and the neighbor has elevation h, then entering the neighbor needs time max(t, h). If that improves the best known time for the neighbor, the algorithm records it and pushes the neighbor into the heap.

The first time the bottom-right cell is popped, its recorded time is the minimum possible maximum elevation on any path from start to finish. That is exactly the earliest time when swimming across is possible.

The complexity is:

• Time: O(n^2 log n) for an n x n grid, because each cell can enter the heap and heap operations cost logarithmic time.
• Extra space: O(n^2) for the best-time table and heap.

Interview follow-ups

How would you solve it with binary search plus BFS?

Binary search on the answer time. For a candidate time t, run BFS or DFS from (0, 0) using only cells whose elevation is <= t. If the bottom-right cell is reachable, try a smaller time; otherwise, try a larger time.

This works because reachability is monotonic: once a time works, every larger time also works. The approach is often easier to explain first because the feasibility check is plain graph traversal.

The tradeoff is repeated work. Each BFS costs O(n^2), and the binary search adds a factor of log(max_elevation), which is O(log n^2) under the usual LeetCode constraints. The heap solution folds those repeated searches into one prioritized traversal.

How would you solve it with union-find?

Sort cells by elevation, then activate them from lowest to highest. Whenever a cell becomes active, union it with any already-active neighbors. The first elevation at which the start cell and end cell belong to the same connected component is the answer.

This works because activating all cells with elevation <= t creates exactly the graph that is swimmable at time t. The moment start and finish connect, there is a valid path using only cells up to that elevation.

The complexity is O(n^2 log n) if the cells are explicitly sorted. Since the original problem says elevations are a permutation from 0 to n^2 - 1, it can also be implemented with an elevation-to-position array and processed in linear order, giving near-O(n^2) time apart from the inverse-Ackermann union-find cost. The tradeoff is more data-structure code than the heap solution.

What if the interviewer asks for the actual path, not just the time?

Keep a parent table alongside best_time. Whenever the algorithm improves a neighbor, store the current cell as that neighbor’s parent. When the target is popped, walk backward from the target through the parent table until reaching the start, then reverse the list.

The correctness does not change because the parent pointers are written only when the best known time improves. The final reconstructed path is one path whose maximum elevation equals the optimal answer. The time complexity stays O(n^2 log n), and the extra space remains O(n^2) with a larger constant for the parent table.

What changes if diagonal moves are allowed?

Only the neighbor generator changes. Add the four diagonal directions to the movement list, then run the same heap algorithm.

The proof still works because the graph has more edges but the path cost is still the maximum elevation along the chosen path. More movement options can only keep the answer the same or make it smaller. The complexity remains O(n^2 log n) for the grid, though each cell now checks eight neighbors instead of four.

Practical takeaway

This problem becomes much easier once it is seen as a minimax path problem: minimize the highest elevation on the path.

Binary search plus BFS is a solid route to the answer, but the heap solution is the clean optimal interview finish. It explores cells by the earliest water level needed to reach them, and the first time it reaches the destination, that water level is the answer.