Problem overview
The method solve receives board, a grid of m rows and n columns with single-letter strings 'X' and 'O', stored as an array of rows. Two 'O' cells are connected when one is directly above, below, left or right of the other; diagonal cells are not connected. A region is a group of 'O' cells reachable from each other through such connections.
A region is surrounded when none of its cells is on the edge of the board, meaning the first or last row or the first or last column. solve captures every surrounded region by turning all its cells into 'X'. A region with a cell on the edge stays as it is. The function changes board in place and returns nothing.
In the first example, the board
X X X X
X O O X
X X O X
X O X X
becomes
X X X X
X X X X
X X X X
X O X X
The three connected 'O' cells in the middle are closed in, so they are captured. The 'O' in the last row is on the edge, so it stays. A board of a single 'O' keeps it, since that cell is on every edge. The algorithm should run in O(m · n) time with O(m · n) extra space.
Approach: start from the edge instead of from each region
The direct idea is to look at each 'O' and search for a path of 'O's to the edge. A large region in the middle of the board would be searched again from each of its cells, which can cost O((m · n)^2).
Turning the question around fixes that. Every 'O' on the edge is safe, and so is every 'O' connected to a safe one. So start one breadth-first search (BFS) from all the edge 'O's at once, and mark every cell it reaches as safe. Each cell joins the queue at most once. After the search, an 'O' that is not marked has no path of 'O's to the edge, so its region is surrounded. One more pass over the board changes those cells to 'X'.
The search uses a queue that the code manages itself, not recursion. A single region can wind through the whole board. On a 200 × 200 board with a snake-shaped region of 19,701 cells, a recursive depth-first version ran out of call stack with the error "Maximum call stack size exceeded", while the queue version handled it.
The board in the third example shows the connection rule: in
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 'O' in the top-left corner touches the region below it only diagonally, so it is a separate region, and it is safe because it is on the edge itself. The middle region winds down to the last row, so it is safe too. The lone 'O' at row 3, column 1 is closed in on all four sides and becomes 'X'.
Step by step
- Read the size.
rowsisboard.length, andcolsisboard[0].length, since every row has the same length. - Create
safe, aboolean[][]of the same size, filled withfalse. It is built withArray.from({length: rows}, ...)and an arrow function so that each row is a separate array. - Create
queue, anumber[][]of[row, column]pairs: the safe cells whose neighbors have not been checked yet. - Scan the whole board with two nested loops over
randc. - Decide if the cell is on the edge:
onBorderis true for the first or last row, or the first or last column. - Seed the search: if the cell is on the edge and holds
'O', setsafe[r][c]totrueand push[r, c]. Marking the cell as it joins the queue means no one adds it twice. - Define
directions: up, down, left and right as[row change, column change]pairs. Each move changes only one coordinate, so diagonal cells are never neighbors. - Keep
head, the index of the next cell to take. Moving an index forward takes cells from the front without shifting the whole array. - Loop while
head < queue.lengthand take the pair athead, destructured intorowandcol, then advancehead. - Visit the four neighbors with
for...ofoverdirections, computingnextRowandnextCol. - Check the bounds before using the neighbor as an index; a cell on the edge has neighbors off the board.
- Spread: if the neighbor holds
'O'and is not yet safe, mark it and push it. - Capture: after the loop, a second pass turns every
'O'that is not safe into'X'.
The solution in TypeScript
class Solution {
solve(board: string[][]): void {
const rows = board.length;
const cols = board[0].length;
const safe: boolean[][] = Array.from({length: rows}, () => new Array(cols).fill(false));
const queue: number[][] = [];
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';
}
}
}
}
}
TypeScript details:
- Why
Array.fromwith a function.new Array(3).fill(new Array(3).fill(false))fills the outer array with the same inner array three times. Setting one cell then shows up in every row: after setting[0][1]the result is[[false,true,false],[false,true,false],[false,true,false]]. The arrow function runs once per row and builds a separate array each time. - Destructuring.
const [row, col] = queue[head]unpacks a two-element array into two constants, andfor (const [dr, dc] of directions)does the same for each move. - In-place change. The method is typed
void. It writes into the array it received, which the caller sees, and it returnsundefined. - Strings, not characters. The cells are strings of length one, compared with
===against'O'. TypeScript has no separate character type. - Erased types.
boolean[][]andnumber[][]are for the compiler only.
Complexity
Time: O(m · n). The seeding pass and the capture pass visit each cell once. In the search each cell joins the queue at most once, because it is marked at that moment, and each one checks four neighbors.
Space: O(m · n). The safe grid has one entry per cell, and the queue holds up to that many pairs.
Edge cases and common mistakes
- A single cell. The board
Ois unchanged, because the cell is on the edge. - Thin boards. With 1 or 2 rows, or 1 or 2 columns, every cell is on the edge, so nothing is captured. A full 3 × 3 board of
'O'keeps all its'O's, because the middle one is connected to the edge. - A lone interior cell. A 3 × 3 board with one
'O'in the middle and'X'everywhere else turns into all'X'. - Diagonal contact. In a plus-shaped board
X O X / O X O / X O X, every'O'is on the edge and nothing changes. Diagonal contact never connects two cells. - A ring. A ring of
'O's closed in by'X'on all sides is a single region, and the whole ring is captured. In a 5 × 5 board with an'X'border, a ring around a central'X'becomes all'X'. - Marking when taking from the queue. Marking a cell only when it leaves the queue lets it be pushed several times by different neighbors. Mark it when it joins.
- Forgetting the bounds check. A neighbor row of -1 or
rowsmakesboard[nextRow]undefined, and reading a cell from it throws "Cannot read properties of undefined". A column out of range does not throw, it just readsundefined, so the bug can stay hidden. - Flipping while searching. Changing cells to
'X'during the search loses the information about which cells are connected to the edge. A separatesafegrid keeps the two steps apart. - Returning a board. The result lives in the board that was passed in; the method returns nothing.
Testing
These boards were run through the solution; each result is the board after the call.
- The four-row example above ends with only the
'O'in the last row. - The single-cell board
OstaysO. - The 5 × 5 board with the winding region keeps every
'O'except the lone one at row 3, column 1. - A 3 × 3 board of all
'O'stays the same. - A 3 × 3 board with
'O'only in the middle becomes all'X'. - The plus-shaped board stays the same.
- A 5 × 5 board with an
'X'border and a ring of'O's around one'X'becomes all'X'.
