Surrounded Regions

Difficulty: Medium

You're given a grid of "X" and "O" characters. Any group of "O"s that is completely surrounded by "X"s - meaning none of the "O"s in that group touch the border of the grid, directly or through other connected "O"s - gets captured: flip every "O" in that group to "X".

Groups of "O"s that do touch the border (even by a single cell) are safe and stay as "O". Modify the grid in place to reflect the result.

Examples

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

The connected group of three O's in the middle never touches a border cell, so it's captured. The lone O in the bottom row is itself on the border, so it survives.

Input: board = [["X"]]
Output: board = [["X"]]

There are no O's, so nothing changes.

Constraints

1 <= rows, cols <= 200

Approach

Testing "is this group of O's surrounded" directly, group by group, is awkward. It's much simpler to flip the question around: find every O that's safe (connected, directly or indirectly, to a border cell), and then capture everything that's left over.

Start a traversal from every "O" sitting on the grid's border, and spread inward through every "O" connected to it. Since these are all reachable from the border, none of them can be captured - mark each one visited with a temporary placeholder (like "#") so it's easy to tell apart from an unvisited "O" later.

Once every border-connected "O" has been marked, make one final pass over the grid: any "O" that's still a plain "O" was never reachable from the border, so it gets captured (flipped to "X"); any cell marked with the placeholder gets flipped back to "O", since it was safe all along.

Solutions

DFS - Recursive Border Flood Fill

Recursively spread out from every border "O", marking each one reached as safe. Then sweep the grid once: unmarked O's are captured, marked cells are restored to O.

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

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

    board[r][c] = "#"; // mark safe

    dfs(r + 1, c);
    dfs(r - 1, c);
    dfs(r, c + 1);
    dfs(r, c - 1);
  }

  for (let r = 0; r < rows; r++) {
    dfs(r, 0);
    dfs(r, cols - 1);
  }
  for (let c = 0; c < cols; c++) {
    dfs(0, c);
    dfs(rows - 1, c);
  }

  for (let r = 0; r < rows; r++) {
    for (let c = 0; c < cols; c++) {
      if (board[r][c] === "O") {
        board[r][c] = "X";
      } else if (board[r][c] === "#") {
        board[r][c] = "O";
      }
    }
  }

  return board;
}

Time: O(rows × cols) · Space: O(rows × cols)

BFS - Iterative Border Flood Fill

Same idea, but push every border "O" into a queue up front and expand outward from all of them together, instead of using recursion.

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

  for (let r = 0; r < rows; r++) {
    for (let c = 0; c < cols; c++) {
      const onBorder = r === 0 || r === rows - 1 || c === 0 || c === cols - 1;
      if (onBorder && board[r][c] === "O") {
        board[r][c] = "#";
        queue.push([r, c]);
      }
    }
  }

  while (queue.length > 0) {
    const [r, c] = queue.shift();
    const neighbors = [[r + 1, c], [r - 1, c], [r, c + 1], [r, c - 1]];

    for (const [nr, nc] of neighbors) {
      if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && board[nr][nc] === "O") {
        board[nr][nc] = "#";
        queue.push([nr, nc]);
      }
    }
  }

  for (let r = 0; r < rows; r++) {
    for (let c = 0; c < cols; c++) {
      if (board[r][c] === "O") {
        board[r][c] = "X";
      } else if (board[r][c] === "#") {
        board[r][c] = "O";
      }
    }
  }

  return board;
}

Time: O(rows × cols) · Space: O(rows × cols)