Swim in Rising Water
You get an n × n grid of heights that holds every number from 0 to n²-1 exactly once, as a list of rows. Rain starts at time 0, and at time t the water stands at height t everywhere, so every cell of height t or less is under water. You start in the top left cell. You can swim from a cell to a cell that shares a side with it when both are under water, and swimming takes no time. Return the earliest time at which you can be in the bottom right cell.
Function
- gridinteger-2d-array
- the heights, as a list of n rows of n numbers
- Returnsinteger
- the earliest time you can reach the bottom right cell
Constraints
n == grid.length == grid[i].length1 ≤ n ≤ 1000 ≤ grid[i][j] ≤ n²-1- Every value from 0 to
n²-1appears exactly once.
Examples
- Input
- grid = [[0, 2], [3, 1]]
- Output
- 2
- Explanation
- Through the top right cell the route is 0, 2, 1, and its highest cell is 2. Through the bottom left cell it is 0, 3, 1, with highest cell 3. At time 2 the first route is under water, so the answer is 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
- Explanation
- At time 15 you can reach the top row and the 5 below its end, but every way out of that area passes 16 or more. Going straight down the right side meets 16 and then 20. Turning left at 16 and going round through 15, 14, 13, 12, 11 and back along the bottom row never climbs above 16, so the answer is 16.
- Input
- grid = [[3, 0], [1, 2]]
- Output
- 3
- Explanation
- The start cell has height 3, so you cannot be in it, and cannot leave it, before time 3. By then the whole grid is under water.
+13 hidden tests on Submit
Follow-up
If heights could repeat and reach 10^9, which of your approaches still works unchanged, and what would you binary search over?
Hints
Open them one at a time. Each one gives away a little more.
Suppose you know the water level
t. Can you tell whether a way through exists? How does that answer change astgrows?A route needs the water to cover every cell on it, so the time a route needs is its highest cell. You want the route between the corners whose highest cell is as low as possible.
Either binary search on
twith a flood fill as the test, or run Dijkstra's algorithm with a min-heap where a cell's time is the larger of the time you arrived with and its own height. Stop when the bottom right cell leaves the heap.
Solution
The time a route needs is its highest cell, because the water has to cover every cell you pass. So the task is to find the route between the corners whose highest cell is as low as possible: a shortest path where a path costs its maximum, not its sum. You can raise the water one step at a time and test, binary search on the water level with the same test, or run Dijkstra's algorithm with the highest cell as the cost.
Raise the water one step at a time
Correct, but does not finish on the largest tests
Intuition
Fix a water level t. The cells you can reach are those of height at most t that connect to the start through such cells. One flood fill from the top left finds them: push the start, pop a cell, push each unvisited neighbour of height at most t. If the bottom right gets visited, time t is enough.
The answer is the smallest t for which the flood fill gets through. It cannot be below the higher corner, max(grid[0][0], grid[n-1][n-1]), since both corners must be under water. Start there and add 1 until the fill succeeds. The first level that works is the answer, because rising water only opens cells and never closes one: a level that works keeps working.
Each test costs O(n²), and the water may rise almost n² times before it gets through. On a 100 × 100 grid that is up to 10^4 levels × 10^4 cells, about 10^8 cell visits. In the large tests the corners hold 0 and 1 and the answers lie between 4,950 and 9,998, so thousands of full flood fills run before the answer turns up.
Algorithm
- Set
tto the higher of the two corner heights. - Flood fill from the top left through cells of height at most
t, with an explicit stack and a visited mark per cell. - If the fill reaches the bottom right, return
t. - Otherwise add 1 to
tand fill again.
def canReach(grid, t):
# True when you can swim from the top left to the bottom right with the water at height t.
n = len(grid)
seen = [[False] * n for _ in range(n)]
seen[0][0] = True
stack = [(0, 0)]
while stack:
r, c = stack.pop()
if r == n - 1 and c == n - 1:
return True
for nr, nc in ((r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)):
if 0 <= nr < n and 0 <= nc < n and not seen[nr][nc] and grid[nr][nc] <= t:
seen[nr][nc] = True
stack.append((nr, nc))
return False
def swimInWater(grid):
n = len(grid)
# You cannot finish before the water covers both corners.
t = max(grid[0][0], grid[n - 1][n - 1])
# Raise the water one step at a time until a way through opens.
while not canReach(grid, t):
t += 1
return tBinary search on the water level
Intuition
The test from the first approach has a useful shape. It fails for every level below the answer and succeeds for every level from the answer on. A yes or no question that flips once, from no to yes, is what binary search finds in a logarithmic number of tries.
Search between lo, the higher corner, and hi = n²-1, the highest cell, where the whole grid is under water and the test must succeed. Test the middle level. If you get through, the answer is at most mid, so set hi = mid; if not, it is above mid, so set lo = mid + 1. When the two meet, that level is the answer.
In the 5 × 5 example lo = 6 and hi = 24. Level 15 fails, because the top area is closed in, so lo = 16. Levels 20, 18, 17 and 16 all succeed, pulling hi down to 16, and the search ends at 16 after five flood fills.
A 100 × 100 grid has 10^4 levels, so about 14 tests decide it, each O(n²): around 1.4 × 10^5 cell visits instead of 10^8. Keep the flood fill iterative. One large test is a winding corridor about 5,000 cells long, far deeper than Python's limit of 1,000 nested calls.
Algorithm
- Set
loto the higher corner height andhiton²-1. - While
lo < hi, takemid = (lo + hi) / 2, rounded down. - Flood fill at level
mid. If it reaches the bottom right, sethi = mid; otherwise setlo = mid + 1. - Return
lo.
def canReach(grid, t):
# True when you can swim from the top left to the bottom right with the water at height t.
n = len(grid)
seen = [[False] * n for _ in range(n)]
seen[0][0] = True
stack = [(0, 0)]
while stack:
r, c = stack.pop()
if r == n - 1 and c == n - 1:
return True
for nr, nc in ((r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)):
if 0 <= nr < n and 0 <= nc < n and not seen[nr][nc] and grid[nr][nc] <= t:
seen[nr][nc] = True
stack.append((nr, nc))
return False
def swimInWater(grid):
n = len(grid)
# The answer lies between the higher corner and the highest cell.
lo = max(grid[0][0], grid[n - 1][n - 1])
hi = n * n - 1
# canReach is false below the answer and true from it on: find the first true.
while lo < hi:
mid = (lo + hi) // 2
if canReach(grid, mid):
hi = mid
else:
lo = mid + 1
return loDijkstra on the highest cell of the route
Intuition
Treat the grid as a graph and give each route a cost: its highest cell, not the sum of its steps. Dijkstra's algorithm still works with that cost, because extending a route never makes it cheaper. The cost of the longer route is max(old cost, new height), never less than the old cost, and that is the one property Dijkstra needs.
Keep a min-heap of cells keyed by their time, the highest cell on the best route found to them. Start with the top left at time grid[0][0]. Pop the cell with the smallest time t; each neighbour you have not seen gets time max(t, its height). When the bottom right leaves the heap, its time is the answer.
You can mark a cell as seen the first time you push it. Cells leave the heap in order of time, so the first cell to reach a neighbour has the smallest time of all the cells that ever will, and the neighbour's time from it is the best possible. A later route arrives with a time at least as large. So each cell enters the heap once, with its final time.
This is the rising water, step by step. The heap holds the edge of the area you can reach, and popping its lowest cell is letting the water rise exactly enough to step there. In the 5 × 5 example the pops run 0, 1, 2, 3, 4, 5, then the gate at 16. After that every cell on the way round gets time 16, and the bottom right leaves the heap with time 16 before anything higher.
Each of the n² cells is pushed and popped at most once, at O(log n) each, so the time is O(n² log n), and the search stops as soon as the target pops.
Algorithm
- Mark the top left as seen and push it with time
grid[0][0]. - Pop the cell with the smallest time
t. If it is the bottom right, returnt. - For each neighbour not seen yet, mark it and push it with time
max(t, its height). - Repeat from step 2.
import heapq
def swimInWater(grid):
n = len(grid)
seen = [[False] * n for _ in range(n)]
seen[0][0] = True
# (time, row, col): the time is the highest cell on the best path found to that cell.
heap = [(grid[0][0], 0, 0)]
while True:
t, r, c = heapq.heappop(heap)
# Cells leave the heap in order of time, so this is the earliest you can be here.
if r == n - 1 and c == n - 1:
return t
for nr, nc in ((r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)):
if 0 <= nr < n and 0 <= nc < n and not seen[nr][nc]:
# Reached for the first time from the cell with the smallest time:
# no later route can arrive earlier, so mark it now.
seen[nr][nc] = True
heapq.heappush(heap, (max(t, grid[nr][nc]), nr, nc))
Pitfalls and edge cases
Most wrong answers come from a forgotten corner, a cost added up instead of maxed, or a search that commits too early.
- Ignoring the start cell's own height. You cannot be in the top left before it is under water, so the answer is at least
grid[0][0]. With[[3, 0], [1, 2]]the answer is 3. - Ignoring the target's height. The bottom right must be under water too, so the answer is at least
grid[n-1][n-1]. - Walking greedily to the lowest neighbour of the current cell. The best route may climb to a gate and then take a long way round, as in the 5 × 5 example. Only a search over the whole edge of the reached area finds it.
- Adding heights along the route, as in an ordinary shortest path. The new time is
max(t, height), nott + height. - Using recursion for the flood fill. A winding route can be thousands of cells long, which breaks Python's limit of 1,000 nested calls.
- Moving diagonally. You can only swim to a cell that shares a side with yours.
Frequently asked questions4
What is the time complexity of Swim in Rising Water?
O(n² log n) with Dijkstra's algorithm: each of the n² cells is pushed and popped at most once on a heap of up to n² entries. Binary search on the water level has the same bound, about log2(n²) flood fills of O(n²) each. Both use O(n²) memory for the visited marks and the heap or stack.
Why does Dijkstra's algorithm work when the cost is the highest cell?
Dijkstra needs one property: extending a route never lowers its cost. Here the new cost is max(t, height), which is never below t, so the property holds. That is why the first time a cell leaves the heap, its time is final and you can stop at the target.
Can Swim in Rising Water be solved with binary search?
Yes. Whether you can get across at level t is false for every level below the answer and true from the answer on. Binary search over t, with a flood fill as the test, finds the answer in about log2(n²) tests: 14 for a 100 × 100 grid.
Can union-find solve Swim in Rising Water?
Yes. Open the cells in order of height, join each new cell with its open neighbours, and stop as soon as the top left and bottom right are in the same set. The height of the cell you opened last is the answer. Since the grid holds each value from 0 to n²-1 once, a table from height to cell gives the opening order without sorting.
Similar problems
Problems that use the same ideas. Solving two or three of them is what makes a pattern stick.
Python
def swimInWater(grid):
# Write code hereCase 1
Case 2
Case 3
Input
grid = [[0, 2], [3, 1]]
Expected
2