Problem overview
solve(board) receives a grid of m rows and n columns, an array of rows where every cell is the letter 'X' or 'O'. Two 'O' cells are connected when one is directly above, below, left or right of the other; diagonals don't count. A region is a group of 'O' cells connected to each other. A region is surrounded when none of its cells is on the edge of the board (first or last row, first or last column).
The function changes every surrounded region to 'X', changes board in place and returns nothing. Regions that touch the edge stay as they are.
In the first example, the three 'O' cells in the upper middle are enclosed and become 'X', while the 'O' in the last row is on the edge and stays:
X X X X
X X X X
X X X X
X O X X
Approach: start from the edge
The direct approach asks, for each 'O', whether some path of 'O' cells leads to the edge. A big region in the middle of the board would be searched again from each of its cells, which can cost O((m · n)^2) in total.
Turning the question around is much cheaper. Every 'O' on the edge is safe, and so is every 'O' connected to a safe one. So start one breadth-first search from all the edge 'O's at once and mark every cell it reaches. Afterwards, any 'O' that is not marked has no path of 'O's to the edge, so its region is surrounded and becomes 'X'. Each cell joins the queue at most once, and two passes over the board finish the job.
The search uses a queue, not recursion. A single region can wind through the whole board, and a recursive search that goes tens of thousands of calls deep overflows the call stack: a recursive flood fill on a 200 by 200 board made only of 'O' cells ends with a RangeError.
Step by step
- Read the size:
rowsisboard.lengthandcolsisboard[0].length. All rows have the same length. - Create
safe, a grid offalsevalues, withArray.from({length: rows}, () => new Array(cols).fill(false)). The arrow function runs once per row, so every row is its own array. - Create
queue, an empty array of[row, column]pairs: the safe cells whose neighbors haven't been checked yet. - Loop over the rows with
r... - ...and inside it over the columns with
c. This first pass finds the edge cells. - Compute
onBorder: the cell is in the first row, the last row, the first column or the last column, with four tests joined by||. - Test for an edge
'O':onBorder && board[r][c] === 'O'. - Mark it:
safe[r][c] = true. Marking a cell as it joins the queue keeps another cell from adding it again. - Push
[r, c]ontoqueue. - Define
directions:[-1, 0],[1, 0],[0, -1]and[0, 1]. Each move changes the row or the column, never both, so diagonal cells are not neighbors. - Declare
headwithlet, starting at 0: the index of the next cell to take fromqueue. Moving an index forward avoidsshift(), which would move all the other elements each time. - Loop while
head < queue.length. - Take the next cell with the destructuring
const [row, col] = queue[head]... - ...and move
headforward withhead++. - Loop over the directions with
for (const [dr, dc] of directions). - Compute the neighbor:
nextRow = row + drandnextCol = col + dc. - Check that it is inside the board, before using it as an index.
- Check that it is an unmarked
'O':board[nextRow][nextCol] === 'O'and!safe[nextRow][nextCol]. - Mark it in
safe... - ...and push
[nextRow, nextCol]ontoqueue. - Second pass: loop over every row...
- ...and every column.
- Capture: if
board[r][c] === 'O' && !safe[r][c], setboard[r][c]to'X'.
The solution in JavaScript
class Solution {
solve(board) {
const rows = board.length;
const cols = board[0].length;
const safe = Array.from({length: rows}, () => new Array(cols).fill(false));
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') {
safe[r][c] = true;
queue.push([r, c]);
}
}
}
const directions = [[-1, 0], [1, 0], [0, -1], [0, 1]];
let head = 0;
while (head < queue.length) {
const [row, col] = queue[head];
head++;
for (const [dr, dc] of directions) {
const nextRow = row + dr;
const nextCol = col + dc;
if (nextRow >= 0 && nextRow < rows && nextCol >= 0 && nextCol < cols) {
if (board[nextRow][nextCol] === 'O' && !safe[nextRow][nextCol]) {
safe[nextRow][nextCol] = true;
queue.push([nextRow, nextCol]);
}
}
}
}
for (let r = 0; r < rows; r++) {
for (let c = 0; c < cols; c++) {
if (board[r][c] === 'O' && !safe[r][c]) {
board[r][c] = 'X';
}
}
}
}
}
JavaScript details to watch:
- Build the grid with a function, not a shared row.
new Array(2).fill(new Array(3).fill(false))puts the same inner array in both places. After setting one cell, it prints[[false,true,false],[false,true,false]]: the mark shows up in every row. WithArray.fromand an arrow function, each row is created separately, and the same mark gives[[false,true,false],[false,false,false]]. - Destructuring.
const [row, col] = queue[head]unpacks a two-element array into two constants, and the same syntax works in thefor...ofheader for[dr, dc]. - In place, no return value. The function changes the arrays it was given, so calling it returns
undefined. The result is read fromboardafterwards. - Cells are strings.
'O'is the letter, not the digit zero, and===compares it exactly.
Trace on a winding region
Take this board:
O X X X X
X O O O X
X X X O X
X O X O X
X X X O X
The first pass finds two 'O' cells on the edge, at [0,0] and [4,3]. The search then reaches the rest of the winding region from the bottom. The queue order is:
0,0 | 4,3 | 3,3 | 2,3 | 1,3 | 1,2 | 1,1
These cells are marked safe, shown as S:
S . . . .
. S S S .
. . . S .
. . . S .
. . . S .
The only unmarked 'O' is at [3,1], closed in by 'X' on all four sides. The second pass turns it into 'X', and the board becomes:
O X X X X
X O O O X
X X X O X
X X X O X
X X X O X
The corner 'O' touches the winding region only diagonally, so it is not part of it, but it is on the edge itself and stays.
Complexity
Time: O(m · n). The first and the last pass visit each cell once. Each cell joins the queue at most once and looks at 4 neighbors, which is constant work.
Space: O(m · n). The safe grid has one entry per cell, and the queue can hold every cell in the worst case.
Edge cases and common mistakes
- A single cell.
[["O"]]staysO: the cell is on every edge. - Boards with a one-cell width or height. Every cell is on the edge, so nothing is captured. A column
X O Xwritten one cell per row stays as it is. - All
'O'. A board full of'O'stays full: every region reaches the edge. - Only
'X'. Nothing to do, and the board is unchanged. - Diagonal neighbors. Using eight directions instead of four would link regions that the problem keeps apart.
- Capturing without the marking pass. Changing an
'O'to'X'as you go loses track of which cells are safe. Keeping a separatesafegrid avoids that. - Returning a new board. The tests read
boarditself, so the function must change it in place.
Testing
- The 4 by 4 board above gives a board that is all
Xexcept theOin the last row. [["O"]]stays[["O"]].X X X / X O X / X X Xbecomes allX.O O O / O X O / O O Ois unchanged, since the ring of'O'cells is on the edge.X O X / X O X / X O Xis unchanged: the column of'O'cells reaches the top and bottom rows.O O / O Ois unchanged.
