The problem. A board holds "X" and "O". A region is a group of "O" cells joined up, down, left or right. A region is surrounded if none of its cells is on the edge of the board — then it's walled in by "X" on every side. Capture every surrounded region by flipping its cells to "X". Change the board in place.
board = [["X","X","X","X"], [["X","X","X","X"],
["X","O","O","X"], -> ["X","X","X","X"],
["X","X","O","X"], ["X","X","X","X"],
["X","O","X","X"]] ["X","O","X","X"]]
The bottom "O" is on the edge, so it is not surrounded and stays.The question sounds like it's about the trapped regions: which O regions are walled in? Answering it directly means walking each region and checking whether any of its cells touches the edge.
Turn it around. The regions that escape are exactly the ones that touch the border — so start there. Walk from every "O" on the border and mark everything you can reach as safe. Whatever is left unmarked can't reach the edge, so it's surrounded. Many grid questions get simpler this way: when the edge decides the answer, begin at the edge and walk inwards.
Walk every "O" region you haven't seen yet, collecting its cells and noting whether any of them is on the border. If none is, flip the whole region. The region list doubles as the BFS queue.
const DIRS = [[-1, 0], [1, 0], [0, -1], [0, 1]]; function solve(board) { const rows = board.length, cols = board[0].length; const seen = board.map((row) => row.map(() => false)); for (let r = 0; r < rows; r++) { for (let c = 0; c < cols; c++) { if (board[r][c] !== "O" || seen[r][c]) continue; // Collect this whole region, noting whether any cell is on the border. const region = [[r, c]]; seen[r][c] = true; let touchesBorder = false; for (let i = 0; i < region.length; i++) { const [cr, cc] = region[i]; if (cr === 0 || cr === rows - 1 || cc === 0 || cc === cols - 1) touchesBorder = true; for (const [dr, dc] of DIRS) { const nr = cr + dr, nc = cc + dc; if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && board[nr][nc] === "O" && !seen[nr][nc]) { seen[nr][nc] = true; region.push([nr, nc]); } } } if (!touchesBorder) for (const [cr, cc] of region) board[cr][cc] = "X"; // surrounded: capture it } }}Time O(m · n), space O(m · n). Each cell joins one region and is looked at once, so it's already linear — but it needs a seen grid, a list per region and a flag, and the capture can only happen after the whole region has been walked.
Walk inwards from every border cell and mark each reachable "O" as "S" (safe). Then sweep the board once: an "O" that was never reached is surrounded, so it becomes "X"; every "S" goes back to "O". The board itself is the visited marker.
Walk in from the border marking safe cells, then capture whatever is left. Try the board with an escape route.
function solve(board) { const rows = board.length, cols = board[0].length; const markSafe = (r, c) => { if (r < 0 || r >= rows || c < 0 || c >= cols || board[r][c] !== "O") return; board[r][c] = "S"; // reachable from the border: safe markSafe(r - 1, c); markSafe(r + 1, c); markSafe(r, c - 1); markSafe(r, c + 1); }; for (let r = 0; r < rows; r++) { // left and right columns markSafe(r, 0); markSafe(r, cols - 1); } for (let c = 0; c < cols; c++) { // top and bottom rows markSafe(0, c); markSafe(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"; // never reached: surrounded else if (board[r][c] === "S") board[r][c] = "O"; // safe: put it back } }}Time O(m · n), space O(m · n). Each "O" is marked at most once, and the final sweep reads every cell once. The only extra memory is the recursion, which is as deep as the longest safe region; use a queue instead if the board can be huge.
Same cost, but the border version needs no seen grid, no region lists and no flags — just one mark and one sweep. That simplicity is the point of the pattern, and in the next lesson it also turns a slow answer into a fast one.
"O" touching a safe one only diagonally is still surrounded.