# LeetCode 778: Swim in Rising Water

## Problem Restatement

We are given an `n x n` grid.

Each cell `grid[i][j]` is the elevation of that square.

Rain starts falling. At time `t`, the water level is also `t`.

We can swim from one cell to a 4-directionally adjacent cell only if both cells have elevation at most `t`.

We start at the top-left cell:

```python
(0, 0)
```

We want to reach the bottom-right cell:

```python
(n - 1, n - 1)
```

Return the minimum time `t` when this becomes possible.

## Input and Output

| Item | Meaning |
|---|---|
| Input | An `n x n` integer grid |
| Output | The minimum time needed to reach the bottom-right cell |
| Movement | Up, down, left, right |
| Rule | A cell is usable at time `t` only if its elevation is `<= t` |
| Constraint | `grid` is a permutation of values from `0` to `n * n - 1` |

Function shape:

```python
class Solution:
    def swimInWater(self, grid: list[list[int]]) -> int:
        ...
```

## Examples

Example 1:

```python
grid = [
    [0, 2],
    [1, 3],
]
```

At time `0`, we can only stand on cell `(0, 0)`.

At time `1`, cell `(1, 0)` becomes available.

At time `2`, cell `(0, 1)` becomes available.

At time `3`, cell `(1, 1)` becomes available.

So the answer is:

```python
3
```

Example 2:

```python
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],
]
```

The answer is:

```python
16
```

There is a path from the top-left to the bottom-right where the highest elevation on the path is `16`.

Before time `16`, that path is not fully available.

## First Thought: Binary Search on Time

One way to solve the problem is to binary search the answer.

For a fixed time `t`, we can ask:

Can we reach the bottom-right cell using only cells with elevation `<= t`?

This can be checked with BFS or DFS.

If we can reach the target at time `t`, then we can also reach it at any later time.

So the answer is monotonic:

| Time | Reachable? |
|---|---|
| Too small | No |
| Large enough | Yes |

This gives a valid solution:

```text
binary search time
for each time, run BFS/DFS
```

But there is a more direct way using a priority queue.

## Problem With Plain BFS

Plain BFS is good when every move has the same cost.

Here, every move takes zero time. The cost of a path is not the number of steps.

The cost of a path is the highest elevation we must wait for.

For example, a longer path with low elevations may be better than a shorter path with one very high elevation.

So we need to minimize this value:

```python
maximum elevation along the path
```

This is a minimax path problem.

## Key Insight

For any path from `(0, 0)` to `(n - 1, n - 1)`, the time needed for that path is the maximum elevation on the path.

So the problem becomes:

Find a path from start to end whose maximum cell value is as small as possible.

This is similar to Dijkstra's algorithm.

Instead of path cost being a sum, path cost is:

```python
max(previous_path_cost, grid[next_row][next_col])
```

We use a min-heap to always expand the reachable cell with the smallest current required time.

Once we pop the bottom-right cell from the heap, we have found the smallest possible time.

## Algorithm

Use a priority queue.

Each heap entry stores:

```python
(time_needed, row, col)
```

Where `time_needed` is the maximum elevation seen along the path to that cell.

Start with:

```python
(grid[0][0], 0, 0)
```

Then:

1. Pop the cell with the smallest `time_needed`.
2. If it is the bottom-right cell, return `time_needed`.
3. Visit its four neighbors.
4. For each unvisited neighbor, compute:

```python
next_time = max(time_needed, grid[nr][nc])
```

5. Push `(next_time, nr, nc)` into the heap.

## Correctness

We prove that the algorithm returns the minimum possible time to reach the bottom-right cell.

The heap always pops the unprocessed cell with the smallest known required time.

For a cell `(r, c)`, the required time of a path to that cell is the maximum elevation along that path. When we move to a neighbor `(nr, nc)`, the required time becomes the larger of the current path cost and `grid[nr][nc]`.

So the algorithm relaxes neighbors using the correct minimax cost rule.

When a cell is popped from the heap, no later path can reach that cell with a smaller required time. Any later path would have to come from a heap entry with required time at least as large as the one just popped. Taking a maximum with another grid value cannot make that required time smaller.

Therefore, when the bottom-right cell is popped, its required time is the smallest possible among all paths from the top-left cell.

That value is exactly the earliest time when the destination can be reached.

## Complexity

| Metric | Value | Why |
|---|---|---|
| Time | `O(n^2 log n)` | There are `n^2` cells, and each heap operation costs `O(log n^2)` |
| Space | `O(n^2)` | The heap and visited set may store all cells |

Since `log(n^2) = 2 log n`, the time complexity is commonly written as:

```python
O(n^2 log n)
```

It is also correct to write:

```python
O(n^2 log(n^2))
```

## Implementation

```python
import heapq

class Solution:
    def swimInWater(self, grid: list[list[int]]) -> int:
        n = len(grid)

        heap = [(grid[0][0], 0, 0)]
        visited = {(0, 0)}

        directions = [
            (1, 0),
            (-1, 0),
            (0, 1),
            (0, -1),
        ]

        while heap:
            time, row, col = heapq.heappop(heap)

            if row == n - 1 and col == n - 1:
                return time

            for dr, dc in directions:
                nr = row + dr
                nc = col + dc

                if nr < 0 or nr >= n or nc < 0 or nc >= n:
                    continue

                if (nr, nc) in visited:
                    continue

                visited.add((nr, nc))
                next_time = max(time, grid[nr][nc])
                heapq.heappush(heap, (next_time, nr, nc))

        return -1
```

## Code Explanation

We use Python's built-in heap:

```python
import heapq
```

The heap starts with the top-left cell:

```python
heap = [(grid[0][0], 0, 0)]
visited = {(0, 0)}
```

The first value in each tuple is the current required time. Since Python heaps sort tuples by the first value, the cell with the smallest required time is popped first.

The movement directions are:

```python
directions = [
    (1, 0),
    (-1, 0),
    (0, 1),
    (0, -1),
]
```

At each step, we pop the best current candidate:

```python
time, row, col = heapq.heappop(heap)
```

If this is the destination, we return immediately:

```python
if row == n - 1 and col == n - 1:
    return time
```

This is safe because the heap processes cells by smallest possible required time.

For each neighbor, we check boundaries:

```python
if nr < 0 or nr >= n or nc < 0 or nc >= n:
    continue
```

We also skip cells we have already added to the heap:

```python
if (nr, nc) in visited:
    continue
```

Then we compute the time needed to reach the neighbor:

```python
next_time = max(time, grid[nr][nc])
```

If the neighbor is higher than everything seen so far, we must wait for it.

Otherwise, the current time is already enough.

Finally, we push the neighbor into the heap:

```python
heapq.heappush(heap, (next_time, nr, nc))
```

## Testing

```python
def run_tests():
    s = Solution()

    assert s.swimInWater([
        [0, 2],
        [1, 3],
    ]) == 3

    assert s.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

    assert s.swimInWater([
        [3, 2],
        [0, 1],
    ]) == 3

    assert s.swimInWater([
        [0],
    ]) == 0

    print("all tests passed")

run_tests()
```

Test coverage:

| Test | Why |
|---|---|
| `[[0,2],[1,3]]` | Small standard case |
| `5 x 5` winding path | Checks that path length is not the cost |
| Start cell has highest value | Checks that answer must be at least `grid[0][0]` |
| Single cell | Start is already the destination |