How do you solve Surrounded Regions on LeetCode?

Surrounded Regions (LeetCode #130) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n) time complexity and O(n) space complexity. Key insight: Regions connected to the border cannot be surrounded.

What is the brute force solution for Surrounded Regions?

The brute force approach for Surrounded Regions is Brute Force, with O(n²) time complexity and O(1) space complexity. The brute force approach involves checking each 'O' cell to see if it is surrounded by 'X' cells. If it is, we change it to 'X'. This method is straightforward but inefficient as it requires multiple passes over the board. The optimal Optimal Solution approach improves this to O(n).

What algorithm or data structure is used to solve Surrounded Regions?

Surrounded Regions uses the following concepts: Array, Depth-First Search, Breadth-First Search, Union-Find, Matrix. The recommended patterns to study are: Depth-First Search, Graph Traversal.

What are the interview tips for Surrounded Regions?

Always clarify the problem and constraints before jumping into coding. Think about edge cases and how they might affect your solution. Explain your thought process clearly while coding to demonstrate your understanding.

What are common mistakes when solving Surrounded Regions?

Failing to check the border cells first. Not handling edge cases like a single row or column.

#130

Surrounded Regions

Medium

ArrayDepth-First SearchBreadth-First SearchUnion-FindMatrixDepth-First SearchGraph Traversal

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(n)
Space	O(1)	O(n)

💡

Intuition

Time O(n)Space O(n)

The optimal approach uses a modified DFS to mark the 'O's that are connected to the borders and cannot be captured. This way, we can efficiently identify which 'O's to change to 'X's in a single pass.

⚙️

Algorithm

3 steps

1Step 1: Iterate through the border cells of the board and perform a DFS for each 'O' found.
2Step 2: Mark all reachable 'O's from the border as a temporary marker (e.g., 'E').
3Step 3: After marking, iterate through the board again to change all 'O's to 'X's and 'E's back to 'O's.

solution.py26 lines

1# Full working Python code
2
3def capture(board):
4    if not board:
5        return
6    rows, cols = len(board), len(board[0])
7    for r in range(rows):
8        for c in range(cols):
9            if (r == 0 or r == rows - 1 or c == 0 or c == cols - 1) and board[r][c] == 'O':
10                dfs(board, r, c)
11    for r in range(rows):
12        for c in range(cols):
13            if board[r][c] == 'O':
14                board[r][c] = 'X'
15            elif board[r][c] == 'E':
16                board[r][c] = 'O'
17
18
19def dfs(board, r, c):
20    if r < 0 or r >= len(board) or c < 0 or c >= len(board[0]) or board[r][c] != 'O':
21        return
22    board[r][c] = 'E'
23    dfs(board, r - 1, c)
24    dfs(board, r + 1, c)
25    dfs(board, r, c - 1)
26    dfs(board, r, c + 1)

ℹ

Complexity note: The time complexity is O(n) because we visit each cell a constant number of times. The space complexity is O(n) due to the recursion stack used in DFS.

1Regions connected to the border cannot be surrounded.
2Using a temporary marker helps to differentiate between captured and non-captured 'O's.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.