Surrounded Regions
Description
You are given an m × n matrix board containing only the characters 'X' and 'O'. Your task is to capture all surrounded regions by modifying the board in-place.
The rules are:
- Connect: A cell is connected to its adjacent cells horizontally or vertically (not diagonally).
- Region: A region is formed by connecting adjacent
'O'cells together. - Surrounded: A region is surrounded if none of the
'O'cells in that region lie on the edge (border) of the board. Such regions are completely enclosed by'X'cells.
To capture a surrounded region, replace all 'O's in that region with 'X's. Any 'O' that is on the border of the board, or connected (directly or indirectly) to a border 'O', should not be captured.
Modify the board in-place. You do not need to return anything.
Examples
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: The 'O' cells at positions (1,1), (1,2), and (2,2) form a connected region. None of these cells are on the border of the board, so the entire region is surrounded and captured — all three become 'X'.
The 'O' at position (3,1) is on the bottom row (the border of the board). Because it touches the edge, it cannot be surrounded and remains 'O'.
Example 2
Input: board = [["X"]]
Output: [["X"]]
Explanation: The board is a single cell containing 'X'. There are no 'O' cells to capture.
Example 3
Input:
board = [
["O","O"],
["O","O"]
]
Output:
[
["O","O"],
["O","O"]
]
Explanation: Every 'O' in this 2×2 board lies on the border (since every cell is an edge cell in a 2×2 grid). None of the 'O' cells are surrounded, so nothing is captured.
Constraints
- m == board.length
- n == board[i].length
- 1 ≤ m, n ≤ 200
- board[i][j] is either 'X' or 'O'
Editorial
Brute Force
Intuition
The most straightforward approach is to directly check every 'O' cell to see if it belongs to a surrounded region.
For each unvisited 'O', we launch a BFS or DFS to explore its entire connected component — the full region of 'O' cells connected to it. During this exploration, we track two things:
- All the cells that belong to this region (so we can flip them later)
- Whether any cell in the region lies on the border of the board
If the region does not touch the border at all, it is surrounded, and we flip every cell in it to 'X'. If it does touch the border, we leave the entire region untouched.
Think of it like inspecting puddles on a field surrounded by walls. You walk over to each puddle, trace its full boundary, and check: "does this puddle leak out to the edge of the field?" If it's completely enclosed, you fill it in.
Step-by-Step Explanation
Let's trace through Example 1:
board = [
["X","X","X","X"],
["X","O","O","X"],
["X","X","O","X"],
["X","O","X","X"]
]
Step 1: Scan the grid from top-left. The first 'O' we encounter is at (1,1). Start BFS from (1,1).
Step 2: BFS from (1,1). Queue: [(1,1)]. Region cells: []. touches_border = false.
- Dequeue (1,1). It is NOT on the border (row 1, col 1 — not first/last row/col). Add to region.
- Neighbors of (1,1): up=(0,1) is 'X', down=(2,1) is 'X', left=(1,0) is 'X', right=(1,2) is 'O' → enqueue (1,2).
- Region: [(1,1)]. Queue: [(1,2)].
Step 3: Dequeue (1,2). Not on border. Add to region.
- Neighbors: up=(0,2) is 'X', down=(2,2) is 'O' → enqueue (2,2), left=(1,1) visited, right=(1,3) is 'X'.
- Region: [(1,1), (1,2)]. Queue: [(2,2)].
Step 4: Dequeue (2,2). Not on border. Add to region.
- Neighbors: up=(1,2) visited, down=(3,2) is 'X', left=(2,1) is 'X', right=(2,3) is 'X'.
- Region: [(1,1), (1,2), (2,2)]. Queue empty. BFS done.
- touches_border = false → This region IS surrounded!
Step 5: Flip all region cells to 'X': board[1][1] = 'X', board[1][2] = 'X', board[2][2] = 'X'.
Step 6: Continue scanning. Next 'O' is at (3,1). Start BFS from (3,1).
- (3,1) is on the border (row 3 is the last row). Set touches_border = true.
- Neighbors: all 'X' or out of bounds. Region = [(3,1)]. touches_border = true.
- Do NOT flip — this region touches the border.
Step 7: Scan complete. Final board:
["X","X","X","X"]
["X","X","X","X"]
["X","X","X","X"]
["X","O","X","X"]
Brute Force — Check Each O-Region Individually — Watch how we BFS from each unvisited 'O' to find its full region, check if it touches the border, and flip it to 'X' if surrounded.
Algorithm
- Create a visited matrix of size m × n, initialized to false
- For each cell (i, j) in the board:
- If board[i][j] is 'O' and not visited:
- Run BFS/DFS to explore the entire connected region of 'O' cells
- Track all cells in the region and whether any cell is on the border
- If no cell in the region is on the border, flip all region cells to 'X'
- If board[i][j] is 'O' and not visited:
- The board is now modified in-place with all surrounded regions captured
Code
#include <vector>
#include <queue>
using namespace std;
class Solution {
public:
void solve(vector<vector<char>>& board) {
int m = board.size();
if (m == 0) return;
int n = board[0].size();
vector<vector<bool>> visited(m, vector<bool>(n, false));
int dirs[4][2] = {{0,1},{0,-1},{1,0},{-1,0}};
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (board[i][j] == 'O' && !visited[i][j]) {
// BFS to find entire region
queue<pair<int,int>> q;
vector<pair<int,int>> region;
bool touchesBorder = false;
q.push({i, j});
visited[i][j] = true;
while (!q.empty()) {
auto [r, c] = q.front();
q.pop();
region.push_back({r, c});
if (r == 0 || r == m-1 || c == 0 || c == n-1) {
touchesBorder = true;
}
for (auto& d : dirs) {
int nr = r + d[0], nc = c + d[1];
if (nr >= 0 && nr < m && nc >= 0 && nc < n
&& board[nr][nc] == 'O' && !visited[nr][nc]) {
visited[nr][nc] = true;
q.push({nr, nc});
}
}
}
if (!touchesBorder) {
for (auto& [r, c] : region) {
board[r][c] = 'X';
}
}
}
}
}
}
};from collections import deque
class Solution:
def solve(self, board: list[list[str]]) -> None:
if not board or not board[0]:
return
m, n = len(board), len(board[0])
visited = [[False] * n for _ in range(m)]
directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]
for i in range(m):
for j in range(n):
if board[i][j] == 'O' and not visited[i][j]:
# BFS to find entire region
queue = deque([(i, j)])
visited[i][j] = True
region = []
touches_border = False
while queue:
r, c = queue.popleft()
region.append((r, c))
if r == 0 or r == m - 1 or c == 0 or c == n - 1:
touches_border = True
for dr, dc in directions:
nr, nc = r + dr, c + dc
if 0 <= nr < m and 0 <= nc < n and board[nr][nc] == 'O' and not visited[nr][nc]:
visited[nr][nc] = True
queue.append((nr, nc))
if not touches_border:
for r, c in region:
board[r][c] = 'X'import java.util.*;
class Solution {
public void solve(char[][] board) {
int m = board.length;
if (m == 0) return;
int n = board[0].length;
boolean[][] visited = new boolean[m][n];
int[][] dirs = {{0,1},{0,-1},{1,0},{-1,0}};
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (board[i][j] == 'O' && !visited[i][j]) {
Queue<int[]> queue = new LinkedList<>();
List<int[]> region = new ArrayList<>();
boolean touchesBorder = false;
queue.offer(new int[]{i, j});
visited[i][j] = true;
while (!queue.isEmpty()) {
int[] cell = queue.poll();
int r = cell[0], c = cell[1];
region.add(cell);
if (r == 0 || r == m - 1 || c == 0 || c == n - 1) {
touchesBorder = true;
}
for (int[] d : dirs) {
int nr = r + d[0], nc = c + d[1];
if (nr >= 0 && nr < m && nc >= 0 && nc < n
&& board[nr][nc] == 'O' && !visited[nr][nc]) {
visited[nr][nc] = true;
queue.offer(new int[]{nr, nc});
}
}
}
if (!touchesBorder) {
for (int[] cell : region) {
board[cell[0]][cell[1]] = 'X';
}
}
}
}
}
}
}Complexity Analysis
Time Complexity: O(m × n)
Each cell is visited at most once thanks to the visited matrix. The outer loop iterates over all m × n cells, and the BFS for each region only visits cells in that region. Since regions are disjoint, the total BFS work across all regions is O(m × n).
Space Complexity: O(m × n)
The visited matrix takes O(m × n) space. The BFS queue and region list can hold up to O(m × n) cells in the worst case (a board full of 'O' cells). Additionally, we store the entire region before deciding whether to flip it.
Why This Approach Is Not Efficient
While the brute force approach has a reasonable O(m × n) time complexity, it has several practical drawbacks:
-
Extra space for region storage: For each region, we collect all cells into a list before deciding whether to flip them. In the worst case (a large region filling most of the board), this list holds nearly m × n entries.
-
Extra visited matrix: We need an entire m × n boolean matrix to track which cells have been processed.
-
Two-pass per region: We first explore the region (to check border contact), then make a second pass to flip cells. This is wasteful.
-
Conceptual complexity: The code has to manage region tracking, border detection, and conditional flipping — three concerns interleaved.
The key insight for a better approach is to reverse the thinking: instead of asking "which regions are surrounded?", ask "which 'O' cells are safe (connected to the border)?" If we mark all safe cells first, then everything left unmarked is surrounded. This eliminates the need for per-region tracking and simplifies the logic significantly.
Optimal Approach - Border DFS (Reverse Thinking)
Intuition
Instead of finding surrounded regions directly, we flip the question around: find all 'O' cells that are NOT surrounded — those are the ones connected to the border.
The idea is beautifully simple:
- Walk along all four borders of the board
- Whenever you find an 'O' on the border, launch a DFS/BFS from it to find ALL 'O' cells connected to this border 'O'
- Temporarily mark all these safe cells with a different character (like '#')
- After processing all borders, sweep the entire board:
- Any remaining 'O' was NOT connected to the border → it's surrounded → flip to 'X'
- Any '#' was connected to the border → it's safe → restore back to 'O'
Think of it like a flood: water enters the board from all border 'O' openings and fills inward through connected 'O' cells. After the flood, any 'O' that stayed dry (unreached by water) is fully enclosed and gets captured.
This approach needs no visited array (we modify the board itself as our marker), no region list, and the logic is cleaner: mark the safe, flip the rest.
Step-by-Step Explanation
Let's trace through Example 1:
board = [
["X","X","X","X"], row 0
["X","O","O","X"], row 1
["X","X","O","X"], row 2
["X","O","X","X"] row 3
]
Step 1: Scan the top border (row 0): X, X, X, X → no 'O' cells. Nothing to mark.
Step 2: Scan the bottom border (row 3): X, O, X, X → found 'O' at (3,1)! Start DFS from (3,1).
Step 3: DFS from (3,1). Mark (3,1) as '#'. Check neighbors:
- Up: (2,1) is 'X' → skip
- Down: out of bounds → skip
- Left: (3,0) is 'X' → skip
- Right: (3,2) is 'X' → skip
DFS done. Only (3,1) is marked '#'.
Step 4: Scan the left border (col 0): X, X, X, X → no 'O'. Nothing to mark.
Step 5: Scan the right border (col 3): X, X, X, X → no 'O'. Nothing to mark.
Step 6: Border scan complete. Board is now:
["X","X","X","X"]
["X","O","O","X"]
["X","X","O","X"]
["X","#","X","X"]
Step 7: Final sweep — go through every cell:
- Any 'O' → surrounded → flip to 'X': (1,1), (1,2), (2,2)
- Any '#' → safe → restore to 'O': (3,1)
- Any 'X' → leave as is
Step 8: Final board:
["X","X","X","X"]
["X","X","X","X"]
["X","X","X","X"]
["X","O","X","X"]
Border DFS — Mark Safe, Then Capture the Rest — Watch how we start DFS from every border 'O', mark all connected safe cells with '#', then sweep the board to capture surrounded regions and restore safe ones.
Algorithm
- Border DFS: For each cell on the four borders of the board:
- If the cell is 'O', run DFS from it
- In the DFS, mark the current cell as '#' (safe)
- Recurse into all 4 neighbors that are 'O'
- Final sweep: Iterate through every cell in the board:
- If the cell is 'O' → it's surrounded → change to 'X'
- If the cell is '#' → it's safe → change back to 'O'
- If the cell is 'X' → leave unchanged
Code
#include <vector>
using namespace std;
class Solution {
public:
void solve(vector<vector<char>>& board) {
int m = board.size();
if (m == 0) return;
int n = board[0].size();
// Step 1: DFS from all border 'O' cells
for (int i = 0; i < m; i++) {
if (board[i][0] == 'O') dfs(board, i, 0, m, n);
if (board[i][n-1] == 'O') dfs(board, i, n-1, m, n);
}
for (int j = 0; j < n; j++) {
if (board[0][j] == 'O') dfs(board, 0, j, m, n);
if (board[m-1][j] == 'O') dfs(board, m-1, j, m, n);
}
// Step 2: Final sweep
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (board[i][j] == 'O') board[i][j] = 'X';
else if (board[i][j] == '#') board[i][j] = 'O';
}
}
}
private:
void dfs(vector<vector<char>>& board, int r, int c, int m, int n) {
if (r < 0 || r >= m || c < 0 || c >= n || board[r][c] != 'O') return;
board[r][c] = '#';
dfs(board, r + 1, c, m, n);
dfs(board, r - 1, c, m, n);
dfs(board, r, c + 1, m, n);
dfs(board, r, c - 1, m, n);
}
};class Solution:
def solve(self, board: list[list[str]]) -> None:
if not board or not board[0]:
return
m, n = len(board), len(board[0])
def dfs(r: int, c: int):
if r < 0 or r >= m or c < 0 or c >= n or board[r][c] != 'O':
return
board[r][c] = '#'
dfs(r + 1, c)
dfs(r - 1, c)
dfs(r, c + 1)
dfs(r, c - 1)
# Step 1: DFS from all border 'O' cells
for i in range(m):
if board[i][0] == 'O':
dfs(i, 0)
if board[i][n - 1] == 'O':
dfs(i, n - 1)
for j in range(n):
if board[0][j] == 'O':
dfs(0, j)
if board[m - 1][j] == 'O':
dfs(m - 1, j)
# Step 2: Final sweep
for i in range(m):
for j in range(n):
if board[i][j] == 'O':
board[i][j] = 'X'
elif board[i][j] == '#':
board[i][j] = 'O'class Solution {
public void solve(char[][] board) {
int m = board.length;
if (m == 0) return;
int n = board[0].length;
// Step 1: DFS from all border 'O' cells
for (int i = 0; i < m; i++) {
if (board[i][0] == 'O') dfs(board, i, 0, m, n);
if (board[i][n - 1] == 'O') dfs(board, i, n - 1, m, n);
}
for (int j = 0; j < n; j++) {
if (board[0][j] == 'O') dfs(board, 0, j, m, n);
if (board[m - 1][j] == 'O') dfs(board, m - 1, j, m, n);
}
// Step 2: Final sweep
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (board[i][j] == 'O') board[i][j] = 'X';
else if (board[i][j] == '#') board[i][j] = 'O';
}
}
}
private void dfs(char[][] board, int r, int c, int m, int n) {
if (r < 0 || r >= m || c < 0 || c >= n || board[r][c] != 'O') return;
board[r][c] = '#';
dfs(board, r + 1, c, m, n);
dfs(board, r - 1, c, m, n);
dfs(board, r, c + 1, m, n);
dfs(board, r, c - 1, m, n);
}
}Complexity Analysis
Time Complexity: O(m × n)
The border scan visits O(m + n) cells. The DFS from border 'O' cells visits each cell at most once (once marked '#', it's never revisited). The final sweep visits all m × n cells once. Total: O(m × n).
Space Complexity: O(m × n) in the worst case for the DFS recursion stack
If the entire board is filled with 'O', the DFS could recurse m × n levels deep. However, no additional data structures (no visited matrix, no region list) are needed beyond the recursion stack — the board itself is used as the marker. For iterative BFS, the queue takes O(m × n) in the worst case, but the key advantage is eliminating the visited matrix and region list that the brute force needed.
Compared to the brute force: we eliminated the visited matrix, eliminated per-region storage, and reduced the logic to a clean two-phase approach. The code is shorter, more elegant, and easier to reason about.