Problem Statement

Surrounded Regions

You are given a grid of cells, each holding the letter 'X' or 'O'. Think of 'X' as a wall and 'O' as open ground. A group of connected 'O' cells is "surrounded" if walls of 'X' close it in on all four sides (up, down, left, right). Your job is to find every surrounded group and fill it in by changing those 'O's into 'X's. The one exception: any 'O' touching the outer edge of the grid can never be surrounded, because there is no wall on the outside. Those edge 'O's, and any 'O's connected to them, stay as 'O'.

mediumGraphsGraphsTime: O(m*n) · Space: O(m*n)

Signals to notice

capture surrounded regionsO on border can't be capturedflood fill from edges

Brute force first

For each 'O' region, check if it touches the border — due to repeated traversals. That direct path helps you understand the question, but it tends to treat every possibility as brand new instead of learning from earlier steps.

The key insight

Start from border 'O' cells and mark them as safe (flood fill). Then scan the grid: unmarked 'O' cells are surrounded (flip to 'X'), safe cells revert to 'O'. The goal is not to be clever for its own sake, but to remember the one relationship that keeps the solution grounded as you move forward.

Trace it on `board=[["X","X","X"],["X","O","X"],["X","X","X"]]`

m=3, n=3. Only 'O' is interior at (1,1); all border cells are 'X'.
DFS over left/right columns: dfs(0,0),dfs(0,2),dfs(1,0),dfs(1,2),dfs(2,0),dfs(2,2) -> all hit 'X', return immediately. No marks.
DFS over top/bottom rows: dfs(0,0),dfs(2,0),dfs(0,1),dfs(2,1),dfs(0,2),dfs(2,2) -> all 'X', return. (1,1) never reached, so no 'T'.
Final scan: (1,1) is 'O' and was not marked safe -> flip to 'X'. No 'T' cells to revert.
Return board=[["X","X","X"],["X","X","X"],["X","X","X"]] (interior region captured).

What must stay true

A region of 'O' is captured if and only if it doesn't touch any border. Starting from border 'O' cells and marking connected 'O' cells as safe identifies exactly the uncapturable regions. As long as that statement keeps holding, you can trust the steps built on top of it.

Shape of the loop

for each border cell: dfs(r, c)        # mark border-connected O's as safe
dfs(r,c): if out-of-bounds or board[r][c] != 'O': return
          board[r][c] = 'T'; recurse up/down/left/right
for each cell: 'O' -> 'X' (surrounded), 'T' -> 'O' (safe)

Pseudocode only — the full worked solution lives in the Solution tab.

Easy way to go wrong

Trying to identify surrounded regions by checking each 'O' cluster — it's easier to identify the UN-surrounded ones (those connected to the border) and capture everything else. Most mistakes here are not about syntax; they come from losing track of what your state, pointer, or structure is supposed to mean.

Graphs Pattern