Repository navigation
116 — Walls and Gates
LeetCode 286 · Medium. Given an m x n grid where -1 is a wall, 0 is a gate, and Int32.max (treated as infinity) is an empty room, fill each empty room with the distance to its nearest gate. Rooms unreachable from any gate stay infinity.
"Distance to the nearest gate" for every room, all at once, has the same shape as Rotting Oranges: instead of rot spreading outward from oranges, distance spreads outward from gates. And exactly as with rotting oranges, running the search forward from every empty room independently redoes an enormous amount of shared work, since neighboring rooms have almost identical nearest-gate searches. Flip the direction: start the BFS from every gate at once, and the first time a room is reached, that's necessarily its shortest distance to some gate — BFS explores in order of distance, so the first arrival is always the closest.
"Fill every cell with its distance to the nearest of several target cells" is the cue for multi-source BFS from the targets, not from each individual cell: seed the queue with every gate/target at once, and the distance each room is first reached at is its shortest path.
For every empty room, run an independent BFS from scratch to find the distance to its nearest gate — none of the work from one room's search is reused for the next.
let INF = Int32.max
func wallsAndGatesBruteForce(_ rooms: inout [[Int]]) {
let rows = rooms.count
guard rows > 0 else { return }
let cols = rooms[0].count
let dirs = [(1,0),(-1,0),(0,1),(0,-1)]
func distanceToNearestGate(_ startR: Int, _ startC: Int) -> Int? {
var visited = Array(repeating: Array(repeating: false, count: cols), count: rows)
var queue = [(startR, startC, 0)]
visited[startR][startC] = true
var head = 0
while head < queue.count {
let (r, c, dist) = queue[head]
head += 1
if rooms[r][c] == 0 { return dist }
for (dr, dc) in dirs {
let nr = r + dr, nc = c + dc
guard nr >= 0, nr < rows, nc >= 0, nc < cols, !visited[nr][nc] else { continue }
guard rooms[nr][nc] != -1 else { continue }
visited[nr][nc] = true
queue.append((nr, nc, dist + 1))
}
}
return nil
}
for r in 0..<rows {
for c in 0..<cols {
if rooms[r][c] == Int(INF) {
if let d = distanceToNearestGate(r, c) {
rooms[r][c] = d
}
}
}
}
}Big-O: O((m·n)²) worst case — up to O(m·n) empty rooms each trigger their own O(m·n) BFS.
Seed a single BFS queue with every gate at once, and expand outward — the first time a room is reached, its distance is locked in, since BFS visits cells in strictly non-decreasing distance order.
func wallsAndGates(_ rooms: inout [[Int]]) {
let rows = rooms.count
guard rows > 0 else { return }
let cols = rooms[0].count
let dirs = [(1,0),(-1,0),(0,1),(0,-1)]
var queue: [(Int, Int)] = []
for r in 0..<rows {
for c in 0..<cols where rooms[r][c] == 0 {
queue.append((r, c))
}
}
var head = 0
while head < queue.count {
let (r, c) = queue[head]
head += 1
for (dr, dc) in dirs {
let nr = r + dr, nc = c + dc
guard nr >= 0, nr < rows, nc >= 0, nc < cols else { continue }
guard rooms[nr][nc] == Int(INF) else { continue }
rooms[nr][nc] = rooms[r][c] + 1
queue.append((nr, nc))
}
}
}
// smoke test
var rooms: [[Int]] = [
[Int(INF), -1, 0, Int(INF)],
[Int(INF), Int(INF), Int(INF), -1],
[Int(INF), -1, Int(INF), -1],
[0, -1, Int(INF), Int(INF)]
]
wallsAndGates(&rooms)
print(rooms)
// [[3, -1, 0, 1], [2, 2, 1, -1], [1, -1, 2, -1], [0, -1, 3, 4]]Big-O: O(m·n) time — every room is enqueued and dequeued at most once across the entire combined traversal. O(m·n) space for the queue.
Running a separate BFS per room means the search from room A and the search from neighboring room B re-explore almost the exact same territory, just shifted by one cell — pure duplicated effort. Seeding the queue with every gate at once eliminates that duplication entirely: each room is discovered exactly once, by whichever gate's expanding frontier reaches it first — and because BFS expands in order of distance, "first to arrive" and "closest gate" are the same thing by construction. This is the identical trick as Rotting Oranges (many sources rotting simultaneously) applied to shortest-distance-to-nearest-target instead of time-to-full-rot.
- Graphs — multi-source BFS guaranteeing shortest distance is exactly the BFS-finds-shortest-path guarantee covered there, just seeded from many starts instead of one.
- BFS — seeding the queue with every gate before expansion begins is the defining move of multi-source BFS.
- Matrix Traversal — the bounds-checked four-directional walk is unchanged from every other grid problem in this chapter.
Walls and Gates is Rotting Oranges with gates instead of rotten oranges — flood outward from every gate at once, and the minute (distance) a room is first reached is its shortest distance to a gate.
- Why does the first time a room is reached during the multi-source BFS guarantee that's its shortest distance to any gate — what would break if DFS were used instead of BFS?
- Why does seeding the queue with all gates simultaneously produce the correct nearest-gate distance for every room, rather than only the distance to whichever gate happens to be listed first?
- What role does checking
rooms[nr][nc] == Int(INF)(rather than just!= -1) play — what would go wrong if a room already assigned a distance were revisited and overwritten?