Surrounded Regions

Medium#130grid

You get a board of X and O. A group of O cells joined by sides is surrounded when none of them lies on the edge of the board; turn every surrounded O into X, in place. Our board has 4 rows: X X X X X, X O X O X, X O X O O, X X O X X — the answer is X X X X X, X X X O X, X X X O O, X X O X X: the two O on the left are surrounded, the three on the right reach the edge at (2, 4), and (3, 2) is on the edge itself.

130 Surrounded RegionsWalkthrough · 1×

Example: flip the surrounded O cells of a board, walking in from its border first.

012340123XXXXXXOXOXXOXOOXXOXXcall stacktop on the right—
O, not reached from the borderX, or an O flipped to Xon the call stackcurrent cellO next to it, kept nextjoined to the border: K, then O again

First the border: an O there can never be surrounded, and neither can any O joined to it

01/37
restart · back · play · step
Speed
1function solve(board):
2 for each cell (row, col) on the border:
3 if board[row][col] == 'O':
4 keep(row, col)
5 for each cell (row, col) in board:
6 if board[row][col] == 'O':
7 board[row][col] = 'X' // surrounded
8 else if board[row][col] == 'K':
9 board[row][col] = 'O' // joined to the border
10 return board
11
12function keep(r, c):
13 board[r][c] = 'K'
14 for each neighbour (nr, nc) that is 'O':
15 keep(nr, nc)
state
row
–
col
–
r
–
c
–
nr
–
nc
–
click a step to go back

← → step · space play/pause

Why it works

  1. An O is safe exactly when it is joined to an O on the border, so walking in from the border O cells marks every safe O and nothing else.
  2. Checking each O on its own would mean a separate search per cell; one walk from the border settles all of them at once.
  3. The mark K keeps the walk from entering a cell twice and tells the second pass which O cells to keep.

Complexity

Time O(rows × cols): keep enters each cell at most once, and the second pass looks at each cell once. Memory O(rows × cols) at worst, for the call stack.

nextNow solve it yourself, no hints.

Solve on LeetCode ↗

The problem and its statement belong to LeetCode. Here are our own retelling, example and solution. Patterns Hero is not affiliated with LeetCode.