Swim in Rising Water
HardThe problem
grid is an n × n square where grid[r][c] is the height of that cell. At time t the water level is t, and you may stand in any cell whose height is at most t, moving up, down, left or right (moving takes no time). Starting at the top-left cell at time 0, return the earliest time at which you can reach the bottom-right cell.
- Example 1Input: grid = [[0, 2], [1, 3]]Output: 3
The goal cell has height 3, so you cannot be there before time 3. At time 3 the path 0, 1, 3 is open.
- Example 2Input: 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
One route goes along the top row, down to the 5, then the 16, left along that row to 12, down the left side to 10 and along the bottom row to 6. The highest cell on it is 16, and no route avoids everything above 16.
- 1 ≤ n ≤ 50
- Every height from 0 to n² - 1 appears exactly once
Write it in Go. Try for about 20 minutes on paper first, then open one hint at a time.
Try it here
Write Go. Common packages like fmt and sort are imported for you. Keep the function name and inputs the same.
Hints, one at a time
Nudge
The cost of a path is the highest cell on it, not the sum. You want the path whose maximum is smallest.
The idea
Dijkstra-style: heap ordered by the max height seen so far; pop the cheapest cell and push its neighbours with max(current, neighbour). (Binary search + BFS also works.)
Target: O(n² log n) time
Go function shape
func swimInWater(grid [][]int) intReference solution
Tested with go test. Try it yourself first, then compare.
// SwimInWater: you can cross a cell once the water level reaches its height, so a path costs the HIGHEST cell
// on it. Dijkstra with "max" instead of "+": always expand the cell whose path-maximum is smallest.
func SwimInWater(grid [][]int) int {
n := len(grid)
seen := make([][]bool, n)
for i := range seen {
seen[i] = make([]bool, n)
}
h := &cellHeap{{grid[0][0], 0, 0}} // {path maximum, row, col}
for h.Len() > 0 {
cur := heap.Pop(h).([3]int)
level, r, c := cur[0], cur[1], cur[2]
if seen[r][c] {
continue
}
seen[r][c] = true
if r == n-1 && c == n-1 {
return level
}
for _, d := range [][2]int{{1, 0}, {-1, 0}, {0, 1}, {0, -1}} {
nr, nc := r+d[0], c+d[1]
if nr >= 0 && nc >= 0 && nr < n && nc < n && !seen[nr][nc] {
heap.Push(h, [3]int{max(level, grid[nr][nc]), nr, nc})
}
}
}
return -1
}
type cellHeap [][3]int
func (h cellHeap) Len() int { return len(h) }
func (h cellHeap) Less(i, j int) bool { return h[i][0] < h[j][0] }
func (h cellHeap) Swap(i, j int) { h[i], h[j] = h[j], h[i] }
func (h *cellHeap) Push(x any) { *h = append(*h, x.([3]int)) }
func (h *cellHeap) Pop() any {
old := *h
x := old[len(old)-1]
*h = old[:len(old)-1]
return x
}