DSA Studio

Surrounded Regions

medium · graph, bfs, grid

Surrounded Regions

Given a 2D board containing 'X' and 'O', capture all regions surrounded by 'X'. A region is captured by flipping all 'O's that are not connected to the border to 'X'.

Why this is worth learning

Invert the difficult question. Instead of trying to prove each region enclosed, first prove which O cells can escape to the border. The complement is precisely the set to capture.

Before coding: one-minute experiment

Why does an interior O connected by a narrow O corridor to one border cell survive, even when most of its neighbors are X?

Function signature

func Solve(board [][]byte)

Inputs / outputs

  • board: grid of 'X' and 'O'.
  • Return: nothing; mutate board in-place.

Example

Input:
X X X X
X O O X
X X O X
X O X X

Output:
X X X X
X X X X
X X X X
X O X X

Constraints

  • 1 <= rows, cols <= 200
  • The board is rectangular and contains only ASCII bytes X and O. Connections use four orthogonal neighbors.

Core idea (near-solution)

For each O cell, one could search for a path to the border, but cells in the same region would repeat that work. Reverse the question: start from every known escape cell on the border and mark every O reachable from them. Reachability is reversible because grid edges are undirected, so this finds exactly the cells with an escape path. Marking whole safe components handles long corridors that local neighbor counts miss. After exploration, flip only unmarked O cells and restore the temporary safe marker.

Invariant: after BFS from borders, every safe 'O' is marked and should not be flipped.

Algorithm (step-by-step)

  1. For every border cell that is 'O', BFS/DFS and mark all reachable 'O' as safe (e.g., 'S').
  2. Scan the board:
    • Flip remaining 'O' to 'X'.
    • Flip 'S' back to 'O'.

Correctness sketch

The initial queue contains all border O cells, marked safe before insertion. Every subsequently marked cell is an O neighbor of a safe cell, so it has an O-only path to the border. Conversely, for any O cell with such a path, induction along that path from the border shows flood fill marks it. Therefore marked cells are exactly the border-connected O set. The final scan restores precisely those cells to O and changes every other original O to X. No X ever enters the queue, so barriers and the rectangular shape are preserved.

Trace (hand walkthrough)

Trace Walkthrough
Example input:
Input:
X X X X
X O O X
X X O X
X O X X

Output:
X X X X
X X X X
X X X X
X O X X

Walk:
- border O at (3,1) marked safe
- all other O are not border-connected -> flip to X
- restore safe O at (3,1) -> final grid shown

Pitfalls to avoid

  • Flipping border-connected 'O' cells to 'X'.
  • Forgetting to restore temporary marks after the flood fill.

Debugging lens

Test a one-row board, one-column board, and a winding escape corridor. Count-based local rules cannot establish enclosure. Temporary S markers must all disappear before return.

Complexity

  • Time: O(r*c)
  • Extra space: O(r*c) worst-case for the queue.

Implementation notes (Go)

  • Mark border-connected 'O' as a temporary value (e.g., 'S').
  • After flood fill, flip remaining 'O' to 'X' and restore 'S'.

Reconstruction checkpoint

On rows XXXX / XOOX / XXOX / XXOX, which O cells survive? If the bottom-row O is changed to X, what changes and why?

Model answer

All four O cells survive initially: (3,2) is on the border and reaches (2,2), (1,2), and (1,1). Closing that single exit makes the remaining three O cells enclosed, so all flip to X. The decision depends on a complete escape path, not the number of adjacent X cells.

Return to Graph General · Module quiz

Run tests to see results
No issues detected
    Join Discord