The problem
An n × n grid gives the height of each square. Rain falls; at time t the water is t deep everywhere, and you can swim between neighbouring squares (up, down, left, right) only if both are at most t high. Swimming takes no time.
Starting at the top-left square, return the least time at which you can reach the bottom-right one.
Examples
- Input
grid = [[0, 2], [1, 3]]
- Output
3
- 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
Constraints
- 1 ≤ n ≤ 50
- 0 ≤ grid[i][j] < n², and every height is different.
The idea
A route can be swum once the water covers its highest square. So the question is the route whose highest square is lowest.
That is Dijkstra’s algorithm with a different cost: a route’s cost is the largest height along it, not the sum. Pull the cheapest frontier square from a min-heap; its neighbours cost the larger of that and their own height. The first time the bottom-right square comes off the heap, its cost is the answer.
- Time
- O(n² log n)
- Space
- O(n²)
Solution · every language run against every case
class Solution: def swimInWater(self, grid: List[List[int]]) -> int: n = len(grid) # Like Dijkstra, but a route's cost is its highest cell, not its sum: always extend # the route whose highest cell is lowest. heap = [(grid[0][0], 0, 0)] seen = {(0, 0)} while heap: t, r, c = heappop(heap) if (r, c) == (n - 1, n - 1): return t for x, y in ((r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)): if 0 <= x < n and 0 <= y < n and (x, y) not in seen: seen.add((x, y)) heappush(heap, (max(t, grid[x][y]), x, y)) return -1