Surrounded Regions

1. Define the problem

You are given an m x n board containing 'X' and 'O'. Capture every region of 'O's that is completely surrounded by 'X' — flip its cells to 'X' — by connecting the region to a border cell. An 'O' (and every 'O' connected to it, 4-directionally) is safe from capture only if that connected group touches the edge of the board. Run depth-first search from every border 'O' , marking everything it touches as safe, then flip every unmarked 'O' to 'X' .

Constraints

m == board.length
n == board_i.length
1 ≤ m, n ≤ 200

Example

Inputboard = [['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 O at (3,1) touches the border and stays. The group at (1,1),(1,2),(2,2) never touches a border, so it is captured and flipped to X.

2. Visualize the solution

One cell per 'O' on the board, labelled by its flat index

10O

13O

Statusmark border O

(3,1) sits on the border — it, and everything connected to it, is safe.

What happens in this step

border scan finds index 13  →  board[13] = 'O', row 3 = last row (border)

dfs(index 13): mark safe[13] = true
  down  → out of bounds
  up    → index 9 = 'X', skip
  right → index 14 = 'X', skip
  left  → index 12 = 'X', skip

Index 13 sits on the border, so it's automatically safe. None of its neighbors are 'O', so the search stops here — this group is just one cell.

Step 1 of 4

Steps to visualize

The row has one slot for each of the four 'O' cells on the board. The label is the cell's position counted flat across the board (0-15); the value is what that cell holds right now.
Every other cell is already an 'X' and never changes, so it gets no slot.
Run depth-first search from every 'O' sitting on the border of the board.
Mark every cell that search reaches as safe — it can never be captured.
Scan the whole board: any 'O' that was never marked safe gets flipped to 'X'.
Cells already marked safe, and every original X, are left untouched.

3. Walk through the code

Walk through the code

Same walkthrough, now with the code. Press Next to move one step and watch which lines run.

One cell per 'O' on the board, labelled by its flat index

10O

13O

Statusmark border O

(3,1) sits on the border — it, and everything connected to it, is safe.

What happens in this step

border scan finds index 13  →  board[13] = 'O', row 3 = last row (border)

dfs(index 13): mark safe[13] = true
  down  → out of bounds
  up    → index 9 = 'X', skip
  right → index 14 = 'X', skip
  left  → index 12 = 'X', skip

Index 13 sits on the border, so it's automatically safe. None of its neighbors are 'O', so the search stops here — this group is just one cell.

Step 1 of 4

4. Solution

Solution

solution.tsTypeScript

function solve(board) {
  const rows = board.length;
  const cols = board[0].length;
  const safe = Array.from({ length: rows }, () => new Array(cols).fill(false));

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

    safe[r][c] = true;
    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);
  }

  return board.map((row, r) => row.map((cell, c) => (cell === 'O' && !safe[r][c] ? 'X' : cell)));
}

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

5. Test cases

Test cases

Input	Expected	Covers
`board = [['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']]`	example from the docstring
`board = [['X','X'],['X','X']]`	`[['X','X'],['X','X']]`	no O cells at all, board is unchanged
`board = [['O','O'],['O','O']]`	`[['O','O'],['O','O']]`	every O is on the border in a 2x2 board, none are captured
`board = [['O']]`	`[['O']]`	a single cell is always a border cell
`board = [['X']]`	`[['X']]`	a single X cell, nothing to capture
`board = [['X','X','X'],['X','O','X'],['X','X','X']]`	`[['X','X','X'],['X','X','X'],['X','X','X']]`	a single interior O with no border connection is captured
`board = [['X','X','X','X'],['X','O','O','X'],['X','O','O','X'],['O','X','X','X']]`	`[['X','X','X','X'],['X','X','X','X'],['X','X','X','X'],['O','X','X','X']]`	one interior region is captured while a separate border O survives

Surrounded Regions