Your free access ends in 7 days — and you haven’t tried it yet. Watch one algorithm run, start to finish. It takes about two minutes.

Try one problem
0
Problem

Surrounded Regions

LeetCode #130Medium
Border-connected O's are safe

Given a grid of X and O cells, flip to X every region of O cells that is fully surrounded, that is, any region not connected 4-directionally to an O on the grid border.

Asked atAmazonGoogle
step 1 / 10
4 × 4 board
X
X
X
X
X
O
O
X
X
X
O
X
X
O
X
X
Border flood + capture sweep
▸
1markSafe(r, c):
2    safe[r][c] = true
3    for each O-neighbour not safe: markSafe
4for each border cell that is 'O':
5    markSafe(r, c)
6// capture sweep
7for each cell (r, c):
8    if grid[r][c]=='O' and not safe: grid[r][c]='X'
9return grid
state
  • ruleborder-connected O ⇒ safe

line 1Capture surrounded regions. An 'O' survives only if it can reach the BORDER through other O's; any O-region sealed inside the board gets flipped to 'X'. The slick trick: instead of testing each region for surroundedness, we flood from the border inward to mark the SAFE O's first — then everything still O afterwards must be captured.