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

Solution❯

Case 1: 'O's on the border

If an 'O' is located directly on the border of the matrix (top row, bottom row, left column, or right column), it cannot be surrounded by 'X's. Therefore, any 'O' on the border and all 'O's connected to it should not be converted to 'X'. We mark these 'safe' regions with a temporary character, such as '#'.

Case 2: 'O's connected to the border

These are internal 'O's that are directly or indirectly connected to border 'O's. For example, if (1, 1) is connected to (0, 1), and (0, 1) is a border 'O', then (1, 1) is also safe. During DFS/BFS from border 'O's, we traverse and mark all such connected 'O's as '#'.

Case 3: Truly surrounded 'O's

After all border-connected 'O's have been marked, any remaining 'O' in the matrix is truly surrounded by 'X's. These should be converted to 'X' as they are not safe. This step is done in a final traversal where we check every cell:

If it is 'O', we change it to 'X'.
If it is '#', we change it back to 'O'.

Final Matrix

The result is a matrix where all the 'O's that were truly surrounded by 'X's have been converted, and those connected to the border are left unchanged.

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