Swim in Rising Water

Q: 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. Binary search on the water level has the same bound, about log2(n²) flood fills of O(n²) each. Both use O(n²) memory.

Q: Can Swim in Rising Water be solved with binary search?

Yes. Whether you can get across at level t flips once, from false to true, at the answer. Binary search over t with a flood fill as the test needs about log2(n²) fills, 14 for a 100 × 100 grid.

Q: 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 two corners are in the same set. The height of the cell you opened last is the answer. Since each value from 0 to n²-1 appears once, a table from height to cell gives the order without sorting.

HardShortest paths Heap Binary search

+10

You get an n × n grid of heights that holds every number from 0 to n²-1 exactly once. 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, in no time, to a cell that shares a side with yours when both are under water. Return the earliest time at which you can be in the bottom right cell.

Function

swimInWater(grid: integer-2d-array) → integer

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].length
1 ≤ n ≤ 100
0 ≤ grid[i][j] ≤ n²-1
Every value from 0 to n²-1 appears exactly once.

Examples

Input: grid = [[0, 2], [3, 1]]
Output: 2
Explanation: Through the top right cell the route is 0, 2, 1, with highest cell 2. Through the bottom left it is 0, 3, 1, with highest cell 3. At time 2 the first route is under water.

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.

0 of 3 opened

Solution

A route needs as much time as its highest cell, because the water has to cover every cell you pass. So find the route between the corners whose highest cell is lowest: a shortest path whose cost is the maximum, not the sum. Raise the water step by step, binary search the level, or run Dijkstra's algorithm on that cost.

Raise the water one step at a time

Correct, but does not finish on the largest tests

Intuition

Fix a water level t. One flood fill from the top left, through cells of height at most t, tells you whether the bottom right is reachable. Start t at the higher corner, max(grid[0][0], grid[n-1][n-1]), since both corners must be under water, and add 1 until the fill gets through. Rising water only opens cells, so the first level that works is the answer.

Each fill costs O(n²), and the water may rise almost n² times: on a 100 × 100 grid, up to 10^4 levels × 10^4 cells, about 10^8 cell visits.

Algorithm

Set t to 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 t and 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 t

Binary search on the water level

Intuition

The flood fill test fails for every level below the answer and succeeds for every level from the answer on. Binary search finds that flip, between the higher corner and n²-1, where the whole grid is under water.

In the 5 × 5 example lo = 6 and hi = 24. Level 15 fails, so lo = 16. Levels 20, 18, 17 and 16 all succeed, and the search ends at 16 after five fills.

A 100 × 100 grid has 10^4 levels, so about 14 fills decide it: around 1.4 × 10^5 cell visits instead of 10^8.

Algorithm

Set lo to the higher corner height and hi to n²-1.
While lo < hi, take mid = (lo + hi) / 2, rounded down.
Flood fill at level mid. If it reaches the bottom right, set hi = mid; otherwise set lo = 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 lo

Dijkstra on the highest cell of the route

Intuition

Give each route a cost: its highest cell. Dijkstra's algorithm still works, because extending a route to a cell of height h costs max(old cost, h), never less than the old cost. Keep a min-heap of cells keyed by that time, starting with the top left at grid[0][0]. 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 gives it the smallest time any cell could, and each cell enters the heap once.

The heap holds the edge of the area you can reach, and each pop raises the water exactly enough to step there. In the 5 × 5 example the pops run 0, 1, 2, 3, 4, 5, then the gate at 16, and the bottom right leaves with 16.

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, return t.
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

Ignoring a corner's own height. The answer is at least grid[0][0] and grid[n-1][n-1]: with [[3, 0], [1, 2]] it is 3.
Walking greedily to the lowest neighbour. The best route may climb to a gate and then go the long way round, as in the 5 × 5 example.
Adding heights along the route, as in an ordinary shortest path. The new time is max(t, height), not t + 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.

Frequently asked questions3

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. Binary search on the water level has the same bound, about log2(n²) flood fills of O(n²) each. Both use O(n²) memory.

Can Swim in Rising Water be solved with binary search?

Yes. Whether you can get across at level t flips once, from false to true, at the answer. Binary search over t with a flood fill as the test needs about log2(n²) fills, 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 two corners are in the same set. The height of the cell you opened last is the answer. Since each value from 0 to n²-1 appears once, a table from height to cell gives the order without sorting.

def swimInWater(grid):
    # Write code here

Test #1

Test #2

Test #3

Argument

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

Expected Output

Swim in Rising Water

Function

Constraints

Examples

Hints

Solution

Raise the water one step at a time

Binary search on the water level

Dijkstra on the highest cell of the route

Pitfalls and edge cases

Frequently asked questions3

Similar problems