Surrounded Regions Graph-Based Matrix Problem

Problem Statement❯

Given a 2D matrix of size N x M filled with characters 'O' and 'X', the goal is to replace all 'O' cells that are completely surrounded by 'X' on all four sides (up, down, left, right).

'O's that are on the border or connected to a border 'O' should not be changed. Only 'O's that are fully enclosed by 'X' must be replaced.

Examples❯

Input Matrix	Output Matrix	Description
[["X", "X", "X", "X"], ["X", "O", "O", "X"], ["X", "X", "O", "X"], ["X", "O", "X", "X"]]	[["X", "X", "X", "X"], ["X", "X", "X", "X"], ["X", "X", "X", "X"], ["X", "O", "X", "X"]]	'O's at (1,1), (1,2), (2,2) are surrounded, so flipped
[["O", "O"], ["O", "O"]]	[["O", "O"], ["O", "O"]]	All 'O's are on border or connected to border, so remain unchanged
[["X"]]	[["X"]]	Single cell matrix, no changes
[["O"]]	[["O"]]	Single 'O' on border, not flipped
[]	[]	Empty matrix, no operation
[["X", "X", "X", "X"], ["X", "O", "O", "X"], ["O", "X", "X", "X"], ["X", "O", "X", "O"], ["O", "O", "X", "X"]]	[["X", "X", "X", "X"], ["X", "X", "X", "X"], ["O", "X", "X", "X"], ["X", "O", "X", "O"], ["O", "O", "X", "X"]]	Internal 'O's surrounded and flipped, border-connected 'O's remain

Visualization Player

Solution❯

Understanding the Problem

We are given a 2D matrix filled with characters 'X' and 'O'. The goal is to identify and convert all 'O' regions that are completely surrounded by 'X' into 'X's. An 'O' region is defined as a group of connected 'O's (connected horizontally or vertically).

However, if any 'O' in a region is on the border (top row, bottom row, leftmost column, or rightmost column), or is connected to a border 'O', that region is considered safe and should not be converted.

Step-by-Step Solution with Example

Step 1: Identify and understand the input

Let’s take this input matrix:


X X X X
X O O X
X X O X
X O X X

We need to determine which 'O's are surrounded and which are connected to the border.

Step 2: Mark the border-connected 'O's

Start by checking the border cells. If an 'O' is found on the border, perform a BFS/DFS to mark it and all connected 'O's as safe (we can use a temporary marker like '#').

In our example, matrix[3][1] is an 'O' on the border. It is safe. We mark it as '#'. But this 'O' is not connected to any other 'O', so only this cell gets marked.

Step 3: Traverse the matrix to convert unsafe 'O's

Now scan the entire matrix:

If a cell is 'O', it means it is not connected to any border 'O'. It is unsafe and must be converted to 'X'.
If a cell is '#', it was marked safe earlier and should be converted back to 'O'.

After this step, our matrix becomes:


X X X X
X X X X
X X X X
X O X X

Step 4: Finalize the matrix

Replace all '#' back to 'O'. Now we have the final matrix with all truly surrounded regions converted and border-connected regions preserved.

Edge Cases

Empty matrix: No operation needed.
All 'X's: No changes required.
All 'O's on border: No 'O' should be changed.
Matrix with only 1 row or 1 column: All 'O's are border cells and remain unchanged.

Finally

This problem teaches us how to use graph traversal techniques like DFS or BFS to identify connected components, especially under constraints like "not surrounded." Marking safe regions with a temporary symbol is a common trick in matrix-based problems. Always process border-related constraints first and then use a second pass to finalize the result.

Algorithm Steps❯

Loop through the border rows and columns of the matrix.
If an 'O' is found on the border, start a DFS/BFS from there to mark all connected 'O's as '#'.
After marking, traverse the entire matrix:

If a cell is 'O', change it to 'X'.
If a cell is '#', revert it to 'O'.

Code

JavaScript

function solve(board) {
  const rows = board.length;
  if (rows === 0) return;
  const cols = board[0].length;

  function dfs(r, c) {
    if (r < 0 || c < 0 || r >= rows || c >= cols || board[r][c] !== 'O') return;
    board[r][c] = '#';
    dfs(r + 1, c);
    dfs(r - 1, c);
    dfs(r, c + 1);
    dfs(r, c - 1);
  }

  for (let i = 0; i < rows; i++) {
    if (board[i][0] === 'O') dfs(i, 0);
    if (board[i][cols - 1] === 'O') dfs(i, cols - 1);
  }

  for (let j = 0; j < cols; j++) {
    if (board[0][j] === 'O') dfs(0, j);
    if (board[rows - 1][j] === 'O') dfs(rows - 1, j);
  }

  for (let i = 0; i < rows; i++) {
    for (let j = 0; j < cols; j++) {
      if (board[i][j] === 'O') board[i][j] = 'X';
      if (board[i][j] === '#') board[i][j] = 'O';
    }
  }
  return board;
}

const board = [
  ["X", "X", "X", "X"],
  ["X", "O", "O", "X"],
  ["X", "X", "O", "X"],
  ["X", "O", "X", "X"]
];

console.log("Updated Board:", solve(board));

Time Complexity❯

Case	Time Complexity	Explanation
Best Case	O(m × n)	Even if there are no 'O's in the matrix, the algorithm must check every border element and traverse the matrix once.
Average Case	O(m × n)	Each cell is visited once during border traversal and once during the final transformation, resulting in linear complexity based on the number of cells.
Worst Case	O(m × n)	If the entire matrix is filled with 'O's, DFS/BFS could touch each element multiple times, but the total work remains bounded by O(m × n).

Space Complexity❯

O(m × n)

Explanation: In the worst case, a DFS/BFS queue or recursion stack can hold all cells in the matrix when marking connected regions.

⬅ Previous TopicDistance of Nearest Cell Having 1 - Grid BFS

Next Topic ⮕Number of Enclaves in Grid

Comments

Loading comments...