-
Notifications
You must be signed in to change notification settings - Fork 0
126 — Swim in Rising Water
LeetCode 778 · Hard. You're given an n x n grid where grid[i][j] is the elevation at that cell (a permutation of 0 to n² - 1). At time t, you may walk between two adjacent cells only if both of their elevations are ≤ t. Rain starts at time 0; return the minimum time t such that you can walk from (0, 0) to (n - 1, n - 1).
Reframe "minimum time to have a walkable path" as "minimum, over every possible path from start to end, of that path's highest single cell." Any path is only as fast as its tallest obstacle — you can't cross a cell of elevation 40 at time 39, no matter how low every other cell on the path is. So the goal isn't the usual "minimize the sum of edge weights along a path" (plain Dijkstra) — it's "minimize the maximum elevation encountered along a path," a minimax path problem.
Picture wading across a flooding parking lot dotted with speed bumps of different heights. You don't care about the total height of every bump you step over — you only care about the tallest single bump on your route, because that's the moment the water has to be deep enough for you to still be walking, not swimming over your head. Find the route that minimizes that one worst bump.
"Minimum time/threshold such that a path exists, where a path is blocked cell-by-cell (or edge-by-edge) until the threshold clears it" is the cue for either binary search on the answer (guess a threshold, check reachability with BFS/DFS) or a Dijkstra-style priority-queue expansion where the "distance" being minimized is the running maximum along the path instead of a running sum.
Try every candidate time t, starting from 0 and counting up, running a full BFS/DFS reachability check (using only cells with elevation ≤ t) after each increment, until (n-1, n-1) becomes reachable.
func swimInWaterBruteForce(_ grid: [[Int]]) -> Int {
let n = grid.count
func canReach(_ t: Int) -> Bool {
guard grid[0][0] <= t else { return false }
var visited = Array(repeating: Array(repeating: false, count: n), count: n)
var stack = [(0, 0)]
visited[0][0] = true
let directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
while let (row, col) = stack.popLast() {
if row == n - 1 && col == n - 1 { return true }
for (dr, dc) in directions {
let nr = row + dr, nc = col + dc
if nr >= 0, nr < n, nc >= 0, nc < n, !visited[nr][nc], grid[nr][nc] <= t {
visited[nr][nc] = true
stack.append((nr, nc))
}
}
}
return false
}
var t = 0
while !canReach(t) {
t += 1
}
return t
}
// smoke test
print(swimInWaterBruteForce([[0,2],[1,3]])) // 3Big-O: O(n⁴) — up to n² candidate values of t (elevations range 0 to n² - 1), each triggering a fresh O(n²) grid traversal.
Dijkstra-style priority-queue expansion, but the "distance" tracked per cell is the minimum possible maximum elevation needed to reach it, not a running sum. Always expand the frontier cell with the smallest such value next — exactly like Dijkstra, just with max standing in for + at every relaxation step.
struct Heap<T> {
private var elements: [T] = []
private let areInIncreasingOrder: (T, T) -> Bool
init(sort: @escaping (T, T) -> Bool) {
self.areInIncreasingOrder = sort
}
var isEmpty: Bool { elements.isEmpty }
var count: Int { elements.count }
var peek: T? { elements.first }
mutating func insert(_ value: T) {
elements.append(value)
siftUp(from: elements.count - 1)
}
mutating func extract() -> T? {
guard !elements.isEmpty else { return nil }
elements.swapAt(0, elements.count - 1)
let top = elements.removeLast()
siftDown(from: 0)
return top
}
private mutating func siftUp(from index: Int) {
var child = index
var parent = (child - 1) / 2
while child > 0 && areInIncreasingOrder(elements[child], elements[parent]) {
elements.swapAt(child, parent)
child = parent
parent = (child - 1) / 2
}
}
private mutating func siftDown(from index: Int) {
var parent = index
while true {
let left = 2 * parent + 1
let right = 2 * parent + 2
var candidate = parent
if left < elements.count && areInIncreasingOrder(elements[left], elements[candidate]) {
candidate = left
}
if right < elements.count && areInIncreasingOrder(elements[right], elements[candidate]) {
candidate = right
}
if candidate == parent { return }
elements.swapAt(parent, candidate)
parent = candidate
}
}
}
func swimInWater(_ grid: [[Int]]) -> Int {
let n = grid.count
var minTimeTo = Array(repeating: Array(repeating: Int.max, count: n), count: n)
minTimeTo[0][0] = grid[0][0]
var heap = Heap<(time: Int, row: Int, col: Int)>(sort: { $0.time < $1.time })
heap.insert((time: grid[0][0], row: 0, col: 0))
let directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
while let current = heap.extract() {
if current.row == n - 1 && current.col == n - 1 {
return current.time
}
guard current.time == minTimeTo[current.row][current.col] else { continue } // stale entry
for (dr, dc) in directions {
let nr = current.row + dr, nc = current.col + dc
guard nr >= 0, nr < n, nc >= 0, nc < n else { continue }
let candidateTime = max(current.time, grid[nr][nc]) // "cost" is a running max, not a sum
if candidateTime < minTimeTo[nr][nc] {
minTimeTo[nr][nc] = candidateTime
heap.insert((time: candidateTime, row: nr, col: nc))
}
}
}
return minTimeTo[n - 1][n - 1]
}
// smoke test
print(swimInWater([[0,2],[1,3]])) // 3
print(swimInWater([[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]])) // 16Big-O: O(n² log n) — every one of the n² cells is pushed and popped from the heap a bounded number of times, each heap operation costing O(log n²) = O(log n). O(n²) space for minTimeTo and the heap.
The brute force answers "what's the minimum feasible t?" by testing candidate values of t one at a time from the outside in — each test is a full, independent reachability check that throws away everything learned from the previous (failed) value of t. The optimal approach flips the question around and solves it in a single pass: instead of asking "is t big enough?" repeatedly, it directly computes, for every cell, the smallest possible "worst bump" on any path to it — using the exact same greedy frontier-expansion idea as Dijkstra, just with the relaxation rule swapped from dist[u] + weight to max(dist[u], elevation). Because elevations only ever raise the running maximum (never lower it, the same monotonicity that makes plain Dijkstra's weights work), the smallest-max-elevation cell on the frontier is always safe to finalize next — so one ordered sweep replaces O(n²) independent reachability checks.
- Graphs — the grid is an implicit graph (each cell a node, 4-directional adjacency the edges); this is a single-source "minimax path" variant of shortest-path search on it.
-
Heaps and Priority Queues — the same
Heap<T>used throughout this wiki, here ordering the frontier by "minimum max-elevation-so-far" instead of a running sum. -
Binary Search — an equally valid optimal strategy for this exact problem is binary search on
titself (search over0...n² - 1for the smallest feasible threshold), paired with a BFS/DFS reachability check at each guess — the brute force above is that same idea with the search step removed, checking everytin order instead of bisecting.
Swim in Rising Water is Dijkstra with max instead of + — the "distance" to a cell is the smallest possible tallest-bump-on-the-way-there, and the frontier cell with the smallest such value is always safe to finalize next.
- Why does
candidateTime = max(current.time, grid[nr][nc])correctly capture "the worst elevation encountered so far on this path," and why ismaxthe right operation instead of+here? - The Related Chapters section mentions binary search on
tas an equally valid optimal strategy. Sketch how that version would work (what does each binary-search step check?) and give its Big-O — is it asymptotically better, worse, or the same as the heap-based approach above? - Why is it safe to
return current.timethe moment(n-1, n-1)is popped from the heap, rather than needing to wait until the heap is fully drained?