-
Notifications
You must be signed in to change notification settings - Fork 0
114 — Surrounded Regions
LeetCode 130 · Medium. Given an m x n matrix board containing 'X' and 'O', capture all regions surrounded by 'X' — flip every 'O' that is not connected to a border 'O' (directly or through a chain of adjacent 'O's) into 'X', in place.
The naive reading of "surrounded" is local: look at a cell's four neighbors and see if they're all 'X'. But that's wrong the moment a region of 'O's is bigger than one cell — a cell deep inside a large 'O' region has 'O' neighbors, not 'X' neighbors, yet the whole region can still be surrounded if none of its cells touch the border. "Surrounded" is a property of the entire connected region, not of any single cell. That reframes the problem: instead of asking "is this cell surrounded," flip the question to "which regions touch the border at all" — because anything that touches the border is safe, and by elimination, everything else gets captured.
"Flip cells that are NOT connected to the border" is the cue for flood-filling from the border inward first: find every region reachable from the edges (those are the safe, un-capturable ones), then treat everything else as capturable — rather than trying to test "is this region enclosed" one region at a time.
For every 'O' cell, independently flood-fill outward with no shared visited cache to check whether its region touches the border — cells belonging to the same region get re-explored from scratch for every starting cell inside that region.
func solveBruteForce(_ board: inout [[Character]]) {
let rows = board.count
guard rows > 0 else { return }
let cols = board[0].count
let dirs = [(1,0),(-1,0),(0,1),(0,-1)]
func touchesBorder(_ startR: Int, _ startC: Int) -> Bool {
var localVisited = Set<[Int]>()
var stack = [(startR, startC)]
localVisited.insert([startR, startC])
while let (r, c) = stack.popLast() {
if r == 0 || r == rows - 1 || c == 0 || c == cols - 1 { return true }
for (dr, dc) in dirs {
let nr = r + dr, nc = c + dc
guard nr >= 0, nr < rows, nc >= 0, nc < cols else { continue }
guard board[nr][nc] == "O", !localVisited.contains([nr, nc]) else { continue }
localVisited.insert([nr, nc])
stack.append((nr, nc))
}
}
return false
}
var toFlip: [(Int, Int)] = []
for r in 0..<rows {
for c in 0..<cols {
if board[r][c] == "O" && !touchesBorder(r, c) {
toFlip.append((r, c))
}
}
}
for (r, c) in toFlip {
board[r][c] = "X"
}
}Big-O: O((m·n)²) worst case — a single giant 'O' region spanning the whole grid causes every cell in it to re-trigger a full O(m·n) traversal of the same region.
Run flood fill once, starting from every border 'O' simultaneously, marking every cell it reaches globally as "safe." Then a single pass flips whatever 'O' was never marked safe.
func solve(_ board: inout [[Character]]) {
let rows = board.count
guard rows > 0 else { return }
let cols = board[0].count
let dirs = [(1,0),(-1,0),(0,1),(0,-1)]
var safe = Array(repeating: Array(repeating: false, count: cols), count: rows)
func markSafe(_ startR: Int, _ startC: Int) {
guard board[startR][startC] == "O", !safe[startR][startC] else { return }
var stack = [(startR, startC)]
safe[startR][startC] = true
while let (r, c) = stack.popLast() {
for (dr, dc) in dirs {
let nr = r + dr, nc = c + dc
guard nr >= 0, nr < rows, nc >= 0, nc < cols else { continue }
guard board[nr][nc] == "O", !safe[nr][nc] else { continue }
safe[nr][nc] = true
stack.append((nr, nc))
}
}
}
for r in 0..<rows {
markSafe(r, 0)
markSafe(r, cols - 1)
}
for c in 0..<cols {
markSafe(0, c)
markSafe(rows - 1, c)
}
for r in 0..<rows {
for c in 0..<cols {
if board[r][c] == "O" && !safe[r][c] {
board[r][c] = "X"
}
}
}
}
// smoke test
var board: [[Character]] = [
["X","X","X","X"],
["X","O","O","X"],
["X","X","O","X"],
["X","O","X","X"]
]
solve(&board)
print(board)
// [["X","X","X","X"], ["X","X","X","X"], ["X","X","X","X"], ["X","O","X","X"]]Big-O: O(m·n) time — the global safe grid guarantees each cell is visited at most once across all the border-seeded flood fills combined. O(m·n) space.
The brute force treats each 'O' cell as its own independent question ("does my region reach the border?") and pays for that independence by re-discovering the same region's answer over and over. The optimal version notices that "does this region touch the border" only needs to be answered once per region — and that every region touching the border can be found in one combined sweep by starting the flood fill from the border cells themselves, rather than from the interior. A single global safe grid means once any cell in a region is marked safe, its neighbors are never re-explored to answer the same question again. Flip the traversal's starting point (border-in instead of interior-out) and the quadratic redundancy disappears entirely.
- Graphs — "mark everything reachable from a set of starting points" is exactly the multi-source flood fill covered there.
- Matrix Traversal — the four-directional bounds-checked walk is unchanged from every other grid problem in this chapter; only which cells seed the traversal differs.
-
DFS and Backtracking —
markSafe's explicit stack is an iterative DFS, functionally identical to the recursive flood fills used elsewhere in this chapter.
Surrounded Regions is flood fill run backward — start from the border 'O's (the ones that can never be captured), mark everything they reach as safe, and whatever's left unmarked gets flipped.
- Why is it wrong to flip an
'O'to'X'the moment you find one whose four immediate neighbors are all'X'? Construct a small counterexample region where that local check gives the wrong answer. - Why does seeding
markSafefrom every border cell (not just the four corners) matter — what would go wrong on a board with an'O'in the middle of an edge, sayboard[0][2], if only corners were seeded? - In the optimal solution, why is it safe to flip cells to
'X'only in a final separate pass, rather than flipping them during the same traversal that marks cells safe?
⬅️ Previous: Pacific Atlantic Water Flow · Next: Rotting Oranges ➡️