Surrounded Regions

Medium

Problem

The board contains "X" and "O". Capture every region of "O"s that is completely surrounded by "X" by flipping it to "X". A region touching the border is never captured. Modify the board in place.

Example 1

Input:  [["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"]]

The bottom O touches the border, so it survives.

Test cases

Case 1

Input:    [["X","X","X","X"],["X","O","O","X"],["X","X","O","X"],["X","O","X","X"]]
Expected: [["X","X","X","X"],["X","X","X","X"],["X","X","X","X"],["X","O","X","X"]]

Case 2

Input:    [["X"]]
Expected: [["X"]]

Case 3

Input:    [["O","O"],["O","O"]]
Expected: [["O","O"],["O","O"]]

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
View solutionHide solution1 approach

1. Protect border-connected cells, flip the rest

Time O(R·C)Space O(R·C) recursion worst case

Any "O" connected to the border survives. Mark those from the border as "S", flip remaining "O" to "X", then restore "S" to "O".

function solve(board) {
const R = board.length, C = board[0].length;
const mark = (r, c) => {
if (r < 0 || c < 0 || r >= R || c >= C || board[r][c] !== 'O') return;
board[r][c] = 'S';
mark(r + 1, c); mark(r - 1, c); mark(r, c + 1); mark(r, c - 1);
};
for (let r = 0; r < R; r++) { mark(r, 0); mark(r, C - 1); }
for (let c = 0; c < C; c++) { mark(0, c); mark(R - 1, c); }
for (let r = 0; r < R; r++)
for (let c = 0; c < C; c++)
board[r][c] = board[r][c] === 'S' ? 'O' : 'X';
}