Surrounded Regions
Medium · Graphs · Explanation and code example
Disjoint Set Union
How it works
Treat every 'O' cell as a node in a graph. Two 'O' cells belong to the same region if they are 4-directionally connected.
The key observation:
- Any region of
'O'that touches the border is safe (it cannot be surrounded). - Any region of
'O'that does not touch the border is captured → should become'X'.
So we use DSU (Union-Find) to group connected 'O' cells, and we create one extra dummy node that represents "connected to border".
- Union every border
'O'with the dummy node. - Union every
'O'with its neighboring'O'cells. - Finally, any cell not connected to the dummy node is surrounded → flip to
'X'.
Steps
- Create a
dsufor(ROWS * COLS)cells plus 1 dummy node. - For each cell
(r, c):- If it is not
'O', skip. - Convert
(r, c)to anid:id = r * COLS + c. - If
(r, c)is on the border, unionidwithdummy. - Union
idwith any 4-direction neighbor that is also'O'.
- If it is not
- Traverse the grid again:
- If a cell is
'O'but not connected todummy, flip it to'X'. - Otherwise keep it as
'O'.
- If a cell is
Complexity
- Time complexity:
O(m * n) - Space complexity:
O(m * n)
Where
mis the number of rows andnis the number of columns of theboard.
Things to watch for
Trying to Find Surrounded Regions Directly
The intuitive approach of finding regions completely surrounded by 'X' is error-prone. A region touching any border cell cannot be captured, and checking this condition during a flood fill is complex. The correct approach is to invert the logic: first mark all border-connected 'O' cells as safe, then flip all remaining 'O' cells. This reversal simplifies the problem significantly.
Forgetting to Check All Four Borders
When marking safe regions, you must start DFS/BFS from 'O' cells on all four borders: top row, bottom row, left column, and right column. A common mistake is only checking two opposite edges (like top and bottom) and missing cells connected through the left or right borders. Ensure your initial seeding loop covers all border cells.
Modifying Cells Without a Temporary Marker
If you flip 'O' to 'X' immediately when you find a surrounded region, you may incorrectly process cells that should remain 'O'. The standard approach uses a temporary marker (like 'T') to distinguish between safe 'O' cells and those to be processed. After marking is complete, convert 'T' back to 'O' and remaining 'O' to 'X' in a final pass.
Python code example
from typing import List
class DSU:
def __init__(self, n):
self.Parent = list(range(n + 1))
self.Size = [1] * (n + 1)
def find(self, node):
if self.Parent[node] != node:
self.Parent[node] = self.find(self.Parent[node])
return self.Parent[node]
def union(self, u, v):
pu = self.find(u)
pv = self.find(v)
if pu == pv:
return False
if self.Size[pu] >= self.Size[pv]:
self.Size[pu] += self.Size[pv]
self.Parent[pv] = pu
else:
self.Size[pv] += self.Size[pu]
self.Parent[pu] = pv
return True
def connected(self, u, v):
return self.find(u) == self.find(v)
class Solution:
def solve(self, board: List[List[str]]) -> None:
ROWS, COLS = len(board), len(board[0])
directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]
dsu = DSU(ROWS * COLS + 1)
for r in range(ROWS):
for c in range(COLS):
if board[r][c] != "O":
continue
if (r == 0 or c == 0 or
r == (ROWS - 1) or c == (COLS - 1)
):
dsu.union(ROWS * COLS, r * COLS + c)
else:
for dx, dy in directions:
nr, nc = r + dx, c + dy
if board[nr][nc] == "O":
dsu.union(r * COLS + c, nr * COLS + nc)
for r in range(ROWS):
for c in range(COLS):
if not dsu.connected(ROWS * COLS, r * COLS + c):
board[r][c] = "X"
C++ code example
class DSU {
vector<int> Parent, Size;
public:
DSU(int n) {
Parent.resize(n + 1);
Size.resize(n + 1);
for (int i = 0; i <= n; i++) {
Parent[i] = i;
Size[i] = 1;
}
}
int find(int node) {
if (Parent[node] != node) {
Parent[node] = find(Parent[node]);
}
return Parent[node];
}
bool unionNodes(int u, int v) {
int pu = find(u), pv = find(v);
if (pu == pv) return false;
if (Size[pu] >= Size[pv]) {
Size[pu] += Size[pv];
Parent[pv] = pu;
} else {
Size[pv] += Size[pu];
Parent[pu] = pv;
}
return true;
}
bool connected(int u, int v) {
return find(u) == find(v);
}
};
class Solution {
public:
void solve(vector<vector<char>>& board) {
int ROWS = board.size(), COLS = board[0].size();
DSU dsu(ROWS * COLS + 1);
vector<vector<int>> directions = {{1, 0}, {-1, 0},
{0, 1}, {0, -1}};
for (int r = 0; r < ROWS; r++) {
for (int c = 0; c < COLS; c++) {
if (board[r][c] != 'O') continue;
if (r == 0 || c == 0 ||
r == ROWS - 1 || c == COLS - 1) {
dsu.unionNodes(ROWS * COLS, r * COLS + c);
} else {
for (auto& dir : directions) {
int nr = r + dir[0], nc = c + dir[1];
if (board[nr][nc] == 'O') {
dsu.unionNodes(r * COLS + c, nr * COLS + nc);
}
}
}
}
}
for (int r = 0; r < ROWS; r++) {
for (int c = 0; c < COLS; c++) {
if (!dsu.connected(ROWS * COLS, r * COLS + c)) {
board[r][c] = 'X';
}
}
}
}
};
Source and license
Adapted from NeetCode’s source · MIT license. Node types are supplied by LeetCode where needed.