You are given an m x n matrix board containing letters 'X' and 'O', capture regions that are surrounded:
'O' cell.'X' cells if you can connect the region with 'X' cells and none of the region cells are on the edge of the board.To capture a surrounded region, replace all 'O's with 'X's in-place within the original board. You do not need to return anything.
Example 1:
Input: board = [["X","X","X","X"],["X","O","O","X"],["X","X","O","X"],["X","O","X","X"]]
Output: [["X","X","X","X"],["X","X","X","X"],["X","X","X","X"],["X","O","X","X"]]
Explanation:
In the above diagram, the bottom region is not captured because it is on the edge of the board and cannot be surrounded.
Example 2:
Input: board = [["X"]]
Output: [["X"]]
Constraints:
m == board.lengthn == board[i].length1 <= m, n <= 200board[i][j] is 'X' or 'O'.The key idea in Surrounded Regions is to identify which 'O' cells are truly enclosed by 'X' and which are connected to the board's boundary. Any 'O' connected to the border cannot be captured because it is not fully surrounded. Instead of checking every region individually, an efficient strategy is to start from the border cells and mark all reachable 'O' cells using Depth-First Search (DFS) or Breadth-First Search (BFS). These marked cells are considered safe and should not be flipped.
After marking all border-connected regions, iterate through the grid and convert the remaining 'O' cells to 'X' because they are fully surrounded. Finally, revert the temporary safe marks back to 'O'. Another alternative is using a Union-Find structure to connect border nodes and detect enclosed components. Both strategies process the grid efficiently with linear traversal.
The overall time complexity is O(m × n), where m and n are the grid dimensions.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| DFS / BFS from Border Cells | O(m × n) | O(m × n) (recursion stack or queue) |
| Union-Find | O(m × n α(n)) | O(m × n) |
take U forward
This approach uses Depth-First Search (DFS) to mark all 'O's connected to the boundary as safe. These 'O's cannot be converted to 'X' because they are on the boundary or connected to the boundary. The rest of the 'O's can be safely converted to 'X'.
Time Complexity: O(m * n), Space Complexity: O(m * n) due to the DFS recursion stack.
1class Solution:
2 def solve(self, board: List[List[str]]) -> None:
3 def dfs(row, col):
4 if row < 0 or col < 0 or row >= len(board) or col >= len(board[0]) or board[row][col] != 'O':
5 return
6 board[row][col] = 'A'
7 dfs(row - 1, col)
8 dfs(row + 1, col)
9 dfs(row, col - 1)
10 dfs(row, col + 1)
11
12 m, n = len(board), len(board[0])
13 if m == 0:
14 return
15
16 for i in range(m):
17 if board[i][0] == 'O':
18 dfs(i, 0)
19 if board[i][n - 1] == 'O':
20 dfs(i, n - 1)
21
22 for j in range(n):
23 if board[0][j] == 'O':
24 dfs(0, j)
25 if board[m - 1][j] == 'O':
26 dfs(m - 1, j)
27
28 for i in range(m):
29 for j in range(n):
30 if board[i][j] == 'O':
31 board[i][j] = 'X'
32 elif board[i][j] == 'A':
33 board[i][j] = 'O'In the Python solution, dfs marks border-connected 'O's with 'A'. After processing the board, it swaps 'O's with 'X's and 'A's with 'O's to achieve the desired output.
This approach uses Breadth-First Search (BFS) utilizing a queue to explore 'O's connected to the boundary. This approach is iterative and avoids deep recursion, keeping the method stack usage low.
Time Complexity: O(m * n), Space Complexity: O(m * n) for the queue's maximal use.
1using System;
2using System.Collections.Generic;
public class Solution {
private void Bfs(char[][] board, int row, int col, int m, int n) {
Queue<(int, int)> q = new Queue<(int, int)>();
q.Enqueue((row, col));
board[row][col] = 'A';
while (q.Count > 0) {
var (curRow, curCol) = q.Dequeue();
int[][] directions = new int[][] {
new int[] {1, 0},
new int[] {-1, 0},
new int[] {0, 1},
new int[] {0, -1}
};
foreach (var dir in directions) {
int newRow = curRow + dir[0];
int newCol = curCol + dir[1];
if (newRow >= 0 && newRow < m && newCol >= 0 && newCol < n && board[newRow][newCol] == 'O') {
board[newRow][newCol] = 'A';
q.Enqueue((newRow, newCol));
}
}
}
}
public void Solve(char[][] board) {
int m = board.Length;
if (m == 0) return;
int n = board[0].Length;
for (int i = 0; i < m; i++) {
if (board[i][0] == 'O') Bfs(board, i, 0, m, n);
if (board[i][n - 1] == 'O') Bfs(board, i, n - 1, m, n);
}
for (int j = 0; j < n; j++) {
if (board[0][j] == 'O') Bfs(board, 0, j, m, n);
if (board[m - 1][j] == 'O') Bfs(board, m - 1, j, m, n);
}
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (board[i][j] == 'O') board[i][j] = 'X';
if (board[i][j] == 'A') board[i][j] = 'O';
}
}
}
}Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, Surrounded Regions is a popular medium-level matrix and graph traversal problem that appears in coding interviews at companies like Amazon, Google, and Microsoft. It tests understanding of DFS/BFS on grids and boundary-based reasoning.
The most common optimal approach is to start DFS or BFS from all border cells containing 'O'. These cells and their connected components are marked as safe. After marking, all remaining 'O' cells are flipped to 'X' because they are fully surrounded.
Graph traversal data structures like recursion stacks (for DFS) or queues (for BFS) are typically used. Alternatively, a Union-Find (Disjoint Set Union) structure can help track connectivity between cells and border nodes.
Any 'O' connected to the border cannot be surrounded by 'X'. By marking all border-connected 'O' cells first, we can easily identify which cells should remain unchanged and which ones must be flipped.
C# application of BFS leverages a queue extensively, managing mutable states and directional processing thoroughly across nodes at each array index explored.