Problem overview
The function solve receives board, a list of rows where every cell is the one-letter string 'X' or 'O'. Two 'O' cells are connected when one is directly above, below, left or right of the other; diagonal cells don't count. A region is a group of 'O' cells connected to each other. A region is surrounded when none of its cells lies on the edge of the board, meaning the first or last row or the first or last column. The function turns every cell of every surrounded region into 'X'. Regions that touch the edge stay as they are.
The function changes board in place and returns nothing. For this board:
X X X X
X O O X
X X O X
X O X Xthe three 'O' cells at the top form one region, and none is on the edge, so they are captured. The 'O' in the last row is on the edge, so it stays:
X X X X
X X X X
X X X X
X O X XApproach: start from the edge
The direct approach checks each 'O' and searches for a path of 'O' cells to the edge. A large region in the middle of the board is then searched again from each of its cells, which can cost O((m · n)^2).
It's cheaper to turn the question around. Every 'O' on the edge is safe, and so is every 'O' connected to a safe one. A breadth-first search that starts from all the edge 'O' cells at once marks every safe cell, and each cell joins the queue at most once. After that, one pass over the board turns every 'O' that was not marked into 'X': it has no path of 'O' cells to the edge, so its region is surrounded.
The search uses a queue instead of recursion. One region can wind through the whole board, and Python limits the call stack: its default recursion limit is 1000. A recursive depth-first search on a 200 x 200 board whose 'O' cells form one winding path stops with RecursionError: maximum recursion depth exceeded. A queue lives on the heap and has no such limit.
Take the board with a long region from the edge:
O X X X X
X O O O X
X X X O X
X O X O X
X X X O XThe corner 'O' is on the edge, and so is the 'O' in the last row. From the last row the search climbs through the column and reaches the three 'O' cells of the second row. The cell in the fourth row on the left has only 'X' neighbours and no path to the edge, so it is captured. The result is:
O X X X X
X O O O X
X X X O X
X X X O X
X X X O XThe corner 'O' touches the region only diagonally, but it is on the edge itself, so it stays anyway.
Step by step
- Store the size.
rowsislen(board)andcolsislen(board[0]). Every row has the same length, so the first row gives the width. - Create
safe, a grid of booleans the same size as the board, allFalse. A cell becomesTruewhen it holds an'O'that is connected to the edge. - Create an empty
dequenamedqueue. It holds the safe cells whose neighbours are still to be checked, as(row, column)tuples. - Loop over rows, then columns to find the
'O'cells on the edge. - Compute
onBorder: the cell is in the first row, the last row, the first column or the last column, with the four tests joined byor. - Seed the search. If the cell is on the edge and holds
'O', setsafe[r][c]toTrueand append(r, c)to the queue. Marking at the moment of queuing means no cell is queued twice. - Define
directions, the four moves up, down, left and right as (row change, column change) tuples. - Run the BFS. While the queue is not empty, take a cell from the front with
popleft()and unpack it intorowandcol. - Visit each neighbour. Compute
nextRowandnextColand check that they are inside the board. - Spread. If the neighbour holds
'O'and is not yet marked, mark it and append it to the queue. - Capture. Go over the board again, and set every cell that holds
'O'and is not marked safe to'X'.
The solution in Python
class Solution:
def solve(self, board: List[List[str]]) -> None:
rows = len(board)
cols = len(board[0])
safe = [[False] * cols for _ in range(rows)]
queue = deque()
for r in range(rows):
for c in range(cols):
onBorder = r == 0 or r == rows - 1 or c == 0 or c == cols - 1
if onBorder and board[r][c] == 'O':
safe[r][c] = True
queue.append((r, c))
directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
while queue:
row, col = queue.popleft()
for dr, dc in directions:
nextRow = row + dr
nextCol = col + dc
if 0 <= nextRow < rows and 0 <= nextCol < cols:
if board[nextRow][nextCol] == 'O' and not safe[nextRow][nextCol]:
safe[nextRow][nextCol] = True
queue.append((nextRow, nextCol))
for r in range(rows):
for c in range(cols):
if board[r][c] == 'O' and not safe[r][c]:
board[r][c] = 'X'
The Python details worth a closer look:
- Building the grid.
[[False] * cols for _ in range(rows)]creates a new row for each iteration. The shorter[[False] * cols] * rowsrepeats one row object: afterbad[0][0] = Trueon a 3 x 3 grid built that way, every row reads[True, False, False]. With the comprehension only the first row changes._is the usual name for a loop variable that isn't used. - Chained comparison.
0 <= nextRow < rowschecks both bounds at once. The lower bound matters: a negative index doesn't fail in Python, it counts from the end, sorow[-1]is the last cell and a neighbour "above" the first row would silently read the last row. - Tuple unpacking.
row, col = queue.popleft()andfor dr, dc in directionssplit each tuple into two names. - Modifying the argument.
boardis the caller's list of lists. Assigningboard[r][c] = 'X'changes that object, which is how the function reports its result without returning anything. Its return value isNone. - Truthiness of a deque. An empty
dequeis false, sowhile queue:ends when the search has nothing left to visit.
Complexity
Time: O(m · n). The first pass visits each cell once. Each cell joins the queue at most once and looks at four neighbours. The final pass visits each cell once.
Space: O(m · n). The safe grid has one entry per cell, and the queue can hold a large share of the cells at once.
Edge cases and common mistakes
- A one-cell board.
[['O']]staysO, because the cell is on every edge. - A board with no interior. With one or two rows, or one or two columns, every cell is on the edge, so nothing is ever captured.
- All
'O'on the edge. A 3 x 3 board with'O'everywhere except the middle stays unchanged, and so does one with'O'only on the four edge midpoints. - An isolated centre. The 3 x 3 board with
'X'everywhere except an'O'in the middle becomes all'X'. - Diagonal contact. Diagonal cells are not neighbours, so the move list has only four entries, each changing one coordinate.
- Capturing first. Turning interior
'O'cells into'X'while searching can cut a path that leads to the edge. The solution only marks during the search and changes the board afterwards. - Marking too late. If a cell is marked when it leaves the queue instead of when it enters, the same cell can be queued several times by different neighbours.
- Recursion on large boards. A recursive search can hit the recursion limit of 1000 calls, as described above.
Testing
- The 4 x 4 board above becomes four rows where only the last row keeps an
'O'(in column 1). [['O']]stays[['O']].X X X / X O X / X X Xbecomes all'X'.O O O / O X O / O O Ostays unchanged.X O X / O X O / X O Xstays unchanged: all four'O'cells are on the edge.
