Learn how to solve the Surrounded Regions problem by marking all ‘O’s connected to the border via DFS, then flipping the rest. Two in-place DFS solutions are explained step by step with comments.
Content
[show]
What the Problem Asks
LeetCode 130: Surrounded Regions
You have a 2D board of letters'X'and'O'. You want to flip every'O'that is completely surrounded by'X'on all four sides into an'X'. An'O'is not surrounded if it’s connected (directly or indirectly) to any'O'on the border of the board.In other words:
- Any group of
'O's entirely inside gets turned into'X'.- Any group of
'O's that touches the edge of the board stays'O'.
The Easy Idea
- Find all ‘O’s on the border (top row, bottom row, left column, right column).
- Mark every ‘O’ that connects to those border ‘O’s (using DFS). These are the ones we don’t flip.
- Flip all the other ‘O’s—those that never got marked—into ‘X’.
That way, you only flip the truly enclosed regions.
Solution 1: One Loop Over Every Border Cell
class Solution:
def dfs(self, r, c, visited, rows, cols, board):
# If out of bounds, stop
if r < 0 or r >= rows or c < 0 or c >= cols:
return
# If it's an 'X', stop
if board[r][c] == "X":
return
# If already marked as border-connected, stop
if visited[r][c] == 1:
return
# Mark this 'O' as connected to the border
visited[r][c] = 1
# Recurse up, left, right, down
self.dfs(r - 1, c, visited, rows, cols, board)
self.dfs(r, c - 1, visited, rows, cols, board)
self.dfs(r, c + 1, visited, rows, cols, board)
self.dfs(r + 1, c, visited, rows, cols, board)
def solve(self, board: List[List[str]]) -> None:
"""
Do not return anything, modify board in-place instead.
"""
rows = len(board)
cols = len(board[0])
# 0 = unvisited, 1 = connected-to-border
visited = [[0 for _ in range(cols)] for _ in range(rows)]
# 1. Check every cell on the border
for r in range(rows):
for c in range(cols):
# Is this cell on the outer border?
if r == 0 or c == 0 or r == rows - 1 or c == cols - 1:
# If it's an 'O' and not yet visited, run DFS
if board[r][c] == "O":
if visited[r][c] == 0:
self.dfs(r, c, visited, rows, cols, board)
# 2. Flip all 'O's that were never marked
for r in range(rows):
for c in range(cols):
if board[r][c] == "O" and visited[r][c] == 0:
board[r][c] = "X"
Step-by-Step Explanation
- Build
visitedarray same size asboard, initialized to 0. - Border scan:
- Loop over every cell
(r,c). - If it’s on the very first row, last row, first column, or last column and is an
'O', calldfs.
- Loop over every cell
dfs(r,c)marks the current'O'visited, then does the same for any adjacent'O'.- Final pass:
- Any
'O'still unvisited must be fully surrounded—flip it to'X'.
- Any
Solution 2: Four Separate Border Loops
class Solution:
def dfs(self, r, c, visited, rows, cols, board):
if r < 0 or r >= rows or c < 0 or c >= cols:
return
if board[r][c] == "X":
return
if visited[r][c] == 1:
return
visited[r][c] = 1
self.dfs(r - 1, c, visited, rows, cols, board)
self.dfs(r, c - 1, visited, rows, cols, board)
self.dfs(r, c + 1, visited, rows, cols, board)
self.dfs(r + 1, c, visited, rows, cols, board)
def solve(self, board: List[List[str]]) -> None:
"""
Do not return anything, modify board in-place instead.
"""
rows = len(board)
cols = len(board[0])
visited = [[0 for _ in range(cols)] for _ in range(rows)]
# Upper Row
r, c = 0, 0
for c in range(cols):
if board[r][c] == "O":
if visited[r][c] == 0:
self.dfs(r, c, visited, rows, cols, board)
# Last Row
r, c = rows - 1, 0
for c in range(cols):
if board[r][c] == "O":
if visited[r][c] == 0:
self.dfs(r, c, visited, rows, cols, board)
# First Column
r, c = 0, 0
for r in range(rows):
if board[r][c] == "O":
if visited[r][c] == 0:
self.dfs(r, c, visited, rows, cols, board)
# Last Column
r, c = 0, cols - 1
for r in range(rows):
if board[r][c] == "O":
if visited[r][c] == 0:
self.dfs(r, c, visited, rows, cols, board)
# Flip the interior 'O's that remain unvisited
for r in range(rows):
for c in range(cols):
if board[r][c] == "O" and visited[r][c] == 0:
board[r][c] = "X"Step-by-Step Explanation
- Initialize
visitedto all zeros. - Four border sweeps:
- Go across the top row, bottom row, left column, then right column.
- For each border cell that’s an
'O'and unvisited, calldfs.
dfsmarks all'O's connected to that border cell.- Final sweep:
- Any
'O'still unvisited lies in a fully surrounded region—flip it to'X'.
- Any
Why This Works
- Any
'O'that can’t reach the border (via up/down/left/right moves) is surrounded. - DFS from border cells marks exactly those
'O's that should stay. - All others get flipped in a single final pass.
Time & Space Complexity
- Time Complexity: O(m·n.4)
- Each DFS visits each cell at most once with looking into every direction.
- Space Complexity: O(m·n)
- The
visitedmatrix and call stack (in worst case) can grow to the whole board.
- The
Conclusion
By first marking all 'O' cells connected to the border (the only ones that shouldn’t be flipped), we can safely flip every other 'O' to 'X'. Both solutions run in linear time and update the board in-place. Choose whichever border-traversal style you find more readable!
For any changes to the article, kindly email at code@codeanddebug.in or contact us at +91-9712928220.
