Swim in Rising Water

Find the minimum time to cross a grid where water level rises with time.

graph minimax priority-queue bfs

You are given an N x N grid `grid` where each cell has an elevation `grid[r][c]` (an integer from 0 to N*N-1). Time starts at 0. At time `t`, the water level everywhere is `t`. You can move from one cell to any adjacent cell (up, down, left, right) as long as the destination cell's elevation is less than or equal to the current water level `t`. You start at `(0,0)` at time 0 and want to reach `(N-1, N-1)`. You may wait as long as you like without moving.

Implement the function `swim_in_rising_water(grid)` that returns the earliest possible time at which you can reach the destination.

Constraints:
- `1 <= N <= 50`
- `grid[i][j]` is a permutation of `0` to `N*N-1`.
- Time complexity should be at most O(N^2 log N).

Write only the function. The grid is guaranteed to be a square 2D list of integers.

Constraints

N is between 1 and 50. grid is a square list of lists with each integer from 0 to N*N-1 exactly once. Your solution should run in O(N^2 log N) time.

Example

>>> swim_in_rising_water([[0, 2], [1, 3]])
3
>>> swim_in_rising_water([[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
>>> swim_in_rising_water([[0]])
0

30 points ~20 min

Recent Submissions

No submissions yet — hit Run Tests to try!

Hints

Think of each cell as a node with weight equal to its elevation. The time needed to reach a node is the max of the node's elevation and the time of the neighbor you came from.

Use Dijkstra's algorithm where the distance to a cell is the minimal possible maximum elevation along any path to that cell.

Use a min-heap to always expand the cell with the smallest current 'max elevation so far'. The answer is the distance of the bottom-right cell.

You can also binary search on the answer and check connectivity with BFS/DFS.

Test Results

Press Ctrl+Enter or click Run Tests to execute your code.