Surrounded Regions: Replace Enclosed O Cells with X

72.9k
0

Given an R × C board containing X and O, capture every region of O cells completely surrounded by X.

A region is formed by horizontal and vertical connections between O cells. A region touching any board boundary remains safe. Every remaining enclosed region must be changed from O to X in place.

surronded regions

surronded regions

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 bottom boundary cell remains safe. The middle region has no boundary path, so all middle O cells become X.

Example 2

Input: board = [["X","O","X"],["O","O","X"],["X","X","X"]]

Output: [["X","O","X"],["O","O","X"],["X","X","X"]]

Explanation: Every O cell connects to a boundary O, so no cell gets captured.

Approach 1

Boundary-connected O cells are safe because a surrounded region cannot touch any board border. Depth First Search begins from every boundary O and marks all reachable O cells with a temporary symbol such as #.

After all safe regions are marked, a nested traversal converts the remaining O cells into X and restores every temporary marker to O.

Algorithm

  • Store the row count in R and the column count in C, allowing boundary validation and complete board traversal.

  • Traverse the left and right borders across all rows and start DFS from every cell containing O, since such cells cannot belong to a surrounded region.

  • Traverse the top and bottom borders across all columns and start DFS from every cell containing O, ensuring that all four board borders are covered.

  • End the current DFS call when the row or column lies outside the board or when the current cell does not contain O, as such a cell cannot extend the safe region.

  • Replace the current O with # before exploring neighboring cells. The temporary marker identifies a safe cell and prevents repeated DFS visits.

  • Continue DFS in the upward, downward, left, and right directions to mark every O connected to the boundary.

  • Traverse the complete board using an outer loop for rows and an inner loop for columns, ensuring that every cell is processed.

  • Convert every remaining O into X, as unmarked O cells are fully surrounded. Restore every # to O, as temporary markers represent boundary-connected safe cells.

Dry Run

surrounded-regions-dfs-reference-style

surrounded-regions-dfs-reference-style

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
private:
// Marks boundary-connected cells using DFS.
void markSafe(int row, int col, vector<vector<char>>& board) {
int rows = board.size();
int cols = board[0].size();
// Base case: stop for invalid cells and non-'O' cells.
if (row < 0 || col < 0 || row >= rows || col >= cols || board[row][col] != 'O') {
return;
}
// Mark the current cell as safe.
board[row][col] = '#';
// Move to the upper cell.
markSafe(row - 1, col, board);
// Move to the lower cell.
markSafe(row + 1, col, board);
// Move to the left cell.
markSafe(row, col - 1, board);
// Move to the right cell.
markSafe(row, col + 1, board);
}
public:
// Captures surrounded regions using DFS.
void solve(vector<vector<char>>& board) {
int rows = board.size();
int cols = board[0].size();
// Mark safe cells from the left and right borders.
for (int row = 0; row < rows; row++) {
markSafe(row, 0, board);
markSafe(row, cols - 1, board);
}
// Mark safe cells from the top and bottom borders.
for (int col = 0; col < cols; col++) {
markSafe(0, col, board);
markSafe(rows - 1, col, board);
}
// Flip captured cells and restore safe cells.
for (int row = 0; row < rows; row++) {
for (int col = 0; col < cols; col++) {
// Captured cells are still marked as 'O'.
if (board[row][col] == 'O') {
board[row][col] = 'X';
}
// Safe cells were temporarily marked as '#'.
else if (board[row][col] == '#') {
board[row][col] = 'O';
}
}
}
}
};
// Prints the board.
void printBoard(vector<vector<char>>& board) {
for (vector<char>& row : board) {
for (char cell : row) {
cout << cell << " ";
}
cout << "\n";
}
}
// Driver code.
int main() {
vector<vector<char>> board = {
{'X', 'X', 'X', 'X'},
{'X', 'O', 'O', 'X'},
{'X', 'X', 'O', 'X'},
{'X', 'O', 'X', 'X'}
};
Solution sol;
sol.solve(board);
printBoard(board);
return 0;
}

Complexity Analysis

Time Complexity: O(R×C), where R and C are the board dimensions; every cell is processed a constant number of times.

Space Complexity: O(R×C), where the recursive DFS stack can contain up to R×C cells in the worst case.

Approach 2

Breadth First Search uses a queue to identify safe regions without recursive calls. All boundary O cells serve as starting points, creating a multi-source traversal from the four board edges.

Every reachable O is temporarily marked before queue insertion to prevent duplicate entries. A final nested traversal captures unmarked regions and restores marked safe cells.

Algorithm

  • Store the row count in R and the column count in C, and initialize a queue to manage boundary-connected cells awaiting exploration.

  • Traverse all four borders and add every cell containing O to the queue, since each boundary O represents a safe starting point.

  • Replace every boundary O with # before queue insertion. Early marking prevents duplicate insertion, especially for corner cells.

  • Continue processing while the queue contains cells, ensuring that every safe region connected to any boundary source is explored.

  • Remove the front cell and examine neighboring cells in the upward, downward, left, and right directions.

  • For every in-bounds neighbor containing O, replace the value with # before adding the coordinates to the queue. Early marking ensures that each cell enters the queue only once.

  • Traverse the complete board using an outer loop for rows and an inner loop for columns.

  • Convert every remaining O into X, as no boundary path exists. Restore every # to O, as marked cells belong to safe boundary-connected regions.

Dry Run

surrounded-regions-bfs-reference-style-corrected

surrounded-regions-bfs-reference-style-corrected

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
private:
// Marks boundary-connected cells using DFS.
void markSafe(int row, int col, vector<vector<char>>& board) {
int rows = board.size();
int cols = board[0].size();
// Base case: stop for invalid cells and non-'O' cells.
if (row < 0 || col < 0 || row >= rows || col >= cols || board[row][col] != 'O') {
return;
}
// Mark the current cell as safe.
board[row][col] = '#';
// Move to the upper cell.
markSafe(row - 1, col, board);
// Move to the lower cell.
markSafe(row + 1, col, board);
// Move to the left cell.
markSafe(row, col - 1, board);
// Move to the right cell.
markSafe(row, col + 1, board);
}
public:
// Captures surrounded regions using DFS.
void solve(vector<vector<char>>& board) {
int rows = board.size();
int cols = board[0].size();
// Mark safe cells from the left and right borders.
for (int row = 0; row < rows; row++) {
markSafe(row, 0, board);
markSafe(row, cols - 1, board);
}
// Mark safe cells from the top and bottom borders.
for (int col = 0; col < cols; col++) {
markSafe(0, col, board);
markSafe(rows - 1, col, board);
}
// Flip captured cells and restore safe cells.
for (int row = 0; row < rows; row++) {
for (int col = 0; col < cols; col++) {
// Captured cells are still marked as 'O'.
if (board[row][col] == 'O') {
board[row][col] = 'X';
}
// Safe cells were temporarily marked as '#'.
else if (board[row][col] == '#') {
board[row][col] = 'O';
}
}
}
}
};
// Prints the board.
void printBoard(vector<vector<char>>& board) {
for (vector<char>& row : board) {
for (char cell : row) {
cout << cell << " ";
}
cout << "\n";
}
}
// Driver code.
int main() {
vector<vector<char>> board = {
{'X', 'X', 'X', 'X'},
{'X', 'O', 'O', 'X'},
{'X', 'X', 'O', 'X'},
{'X', 'O', 'X', 'X'}
};
Solution sol;
sol.solve(board);
printBoard(board);
return 0;
}

Complexity Analysis

Time Complexity: O(R×C), where R and C are the board dimensions; every cell enters the queue at most once and the final scan examines all cells.

Space Complexity: O(R×C), where the queue can store up to R×C cell coordinates in the worst case.

Approach 3

Disjoint Set Union represents every board cell using a unique node and introduces one additional virtual boundary node. Every boundary O joins the virtual node, forming a common set for all safe cells.

Adjacent O cells join the same DSU set. After all unions finish, an O cell outside the virtual boundary set has no path to any border and therefore belongs to a surrounded region.

Algorithm

  • Initialize a DSU structure containing R×C+1 nodes. The first R×C nodes represent board cells, while the final node represents the virtual boundary.

  • Map the cell at row r and column c to node identifier r×C+c, allowing board coordinates to be managed through one-dimensional DSU arrays.

  • Traverse the board using an outer loop for rows and an inner loop for columns, ensuring that every cell is examined.

  • Process only cells containing O, since X cells do not participate in region connectivity.

  • Merge every boundary O with the virtual boundary node, allowing all border-connected safe regions to share a common representative.

  • Merge each O with adjacent O cells. Checking only the right and downward neighbors avoids processing the same undirected connection twice.

  • Find the representative of the virtual boundary node after all unions finish.

  • Traverse the board again and compare every O cell’s representative with the virtual boundary representative. Convert the cell to X when the representatives differ, as no connection to a border exists.

Dry Run

surrounded-regions-dsu-code-faithful-corrected

surrounded-regions-dsu-code-faithful-corrected

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
private:
// Finds the parent representative using path compression.
int findParent(int node, vector<int>& parent) {
// Base case: the node is its own parent.
if (parent[node] == node) {
return node;
}
// Compress the path for faster future lookup.
parent[node] = findParent(parent[node], parent);
// Return the ultimate parent.
return parent[node];
}
// Merges two groups using union by size.
void unite(int first, int second, vector<int>& parent, vector<int>& size) {
// Find the parent of the first node.
int parentFirst = findParent(first, parent);
// Find the parent of the second node.
int parentSecond = findParent(second, parent);
// If both nodes are already in one group, stop.
if (parentFirst == parentSecond) {
return;
}
// Keep the larger group as the main parent.
if (size[parentFirst] < size[parentSecond]) {
swap(parentFirst, parentSecond);
}
// Attach the smaller group to the larger group.
parent[parentSecond] = parentFirst;
// Update the size of the merged group.
size[parentFirst] += size[parentSecond];
}
public:
// Captures surrounded regions using DSU.
void solve(vector<vector<char>>& board) {
int rows = board.size();
int cols = board[0].size();
int total = rows * cols;
// This extra node represents all boundary-connected 'O' cells.
int boundary = total;
vector<int> parent(total + 1);
vector<int> size(total + 1, 1);
vector<int> deltaRow = {-1, 1, 0, 0};
vector<int> deltaCol = {0, 0, -1, 1};
// Initially, every node is its own parent.
for (int node = 0; node <= total; node++) {
parent[node] = node;
}
// Merge all connected 'O' cells.
for (int row = 0; row < rows; row++) {
for (int col = 0; col < cols; col++) {
// Skip blocked cells.
if (board[row][col] != 'O') {
continue;
}
int current = row * cols + col;
// Connect boundary 'O' cells to the virtual boundary node.
if (row == 0 || col == 0 || row == rows - 1 || col == cols - 1) {
unite(current, boundary, parent, size);
}
// Check all four adjacent directions.
for (int dir = 0; dir < 4; dir++) {
int nextRow = row + deltaRow[dir];
int nextCol = col + deltaCol[dir];
// Check if the next cell is inside the board.
if (nextRow >= 0 && nextCol >= 0 && nextRow < rows && nextCol < cols) {
// Merge only adjacent 'O' cells.
if (board[nextRow][nextCol] == 'O') {
unite(current, nextRow * cols + nextCol, parent, size);
}
}
}
}
}
// Find the parent of the virtual boundary node.
int boundaryParent = findParent(boundary, parent);
// Flip 'O' cells outside the boundary group.
for (int row = 0; row < rows; row++) {
for (int col = 0; col < cols; col++) {
// Captured 'O' cells are not connected to the boundary.
if (board[row][col] == 'O' && findParent(row * cols + col, parent) != boundaryParent) {
board[row][col] = 'X';
}
}
}
}
};
// Prints the board.
void printBoard(vector<vector<char>>& board) {
for (vector<char>& row : board) {
for (char cell : row) {
cout << cell << " ";
}
cout << "\n";
}

Complexity Analysis

Time Complexity: O(R×C×α(R×C)), where R and C are the board dimensions and α is the inverse Ackermann cost of each optimized DSU operation.

Space Complexity: O(R×C), where the DSU parent and size arrays store all R×C board cells and one virtual boundary node.

Interview follow-up Questions

No. A boundary O always remains safe.

Graph

Read Similar Blogs

Graph

Disjoint Set Union: Union by Rank, Size and Path Compression

Design a disjoint set, also called a union-find data structure, for N nodes numbered from 1 to N . Initially, every node belongs to a separate set. Support the following operations: DisjointSet(int...

89.1k
Graph

Print Shortest Path

Given a weighted undirected graph with n vertices numbered from 1 to n and m edges, find a shortest path from vertex 1 to vertex n . Each edge appears as [u, v, weight] and every weight is positive...

96.1k
Graph

Network Delay Time Using Dijkstra's Algorithm

A network contains n nodes labeled from 1 to n . Each directed edge [u,v,w] means a signal needs w time units to travel from node u to node v . A signal starts from node k . Return the minimum time...

81.2k
Comments0