# Surrounded Regions | DFS Solution Explained

LeetCode 130. Surrounded Regions. I solve the problem using DFS approach. This is more of an implementation based question. Problem Link.

## 0. Surrounded Regions: Problem Discussion

Given a grid of ‘X’ and ‘O’s like such: a grid of X and Os for the problem Surrounded Regions

We focus on ‘O’s. If an O is present on the boundary – or is connected by a chain of ‘O’s to an ‘O’ on the boundary, we keep it as is. However, all the remaining ‘O’s get converted to ‘X’s.

## 1. Surrounded Regions: Observations

### 1.0. Intuition

1. How do we traverse the grid? We have to use BFS/DFS.
2. How do we distinguish between the ‘O’ connected on the boundary to the ‘O’s present inside?
3. How do we keep a track of visited cells?

Core observation: We can answer the questions 2 and 3 together by creating an intermediate state.

• One way is to run a DFS from all the boundary connected ‘O’s and convert them all to an intermediate state, say ‘#’.
• Then, once we are done with the search, we are left with a gird that has the following properties:
• X remain intact
• Os connected on the outside get converted to #s
• Os not connected thus become Xs

### 1.1. Logic

• Initialize a DFS from all the Os on the boundary. For each DFS:
• Continue exploring in all the directions, till you see Os
• Convert all the Os in this case to #s
• Once done, we convert:
• all the remaining Os to Xs
• all the #s to Os

## 2. Surrounded Regions: Code & Complexity Analysis

### 2.0. Code

```class Solution:
def solve(self, board: List[List[str]]) -> None:
"""
Do not return anything, modify board in-place instead.
"""
def dfs(x, y):
if not (0 <= x < m and 0 <= y < n): return

if board[x][y] == 'O':
board[x][y] = '#'
for dx, dy in [(0, 1), (0, -1), (-1, 0), (1, 0)]:
nx, ny = x+dx, y+dy
dfs(nx, ny)

m, n = len(board), len(board)
for x in range(m):
dfs(x, 0)
dfs(x, n-1)
for y in range(n):
dfs(0, y)
dfs(m-1, y)

for x in range(m):
for y in range(n):
if board[x][y] == 'O':
board[x][y] = 'X'
for x in range(m):
for y in range(n):
if board[x][y] == '#':
board[x][y] = 'O'
return```

### 2.1. Complexity Analysis

• Time: O(MN). Worst case, the grid is full of Os and we end up going over all them once.
• Space: O(MN). While we modify the board in-place, the height of the recursion call stack can be O(MN), for the case described above.

##### Tanishq Chaudhary Producing high-quality intuitive explanations of interview problems. Currently covering LeetCode and InterviewBit.

### Recommended Posts

##### Gas Station | InterviewBit | Solution Explained

June 13, 2022

##### Disjoint Intervals | InterviewBit | Solution Explained

June 12, 2022

##### Capture Regions on Board | InterviewBit | Solution Explained

May 13, 2022

This site uses Akismet to reduce spam. Learn how your comment data is processed.