Surrounded Regions
Medium · Matrix · Array · Depth-First Search · Breadth-First Search · Union Find · Matrix
Problem
You are given an m x n board of 'X' and 'O' characters. A *region* is a group of 'O' cells connected horizontally or vertically. A region is captured when none of its cells lies on the border of the board, meaning it is fully enclosed by 'X' cells.
Capture every enclosed region by replacing all of its 'O's with 'X'. Modify board in place; regions that reach the border stay untouched.
Examples
Input: board = [["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"]]
The three connected inner O's are enclosed and flip; the O on the bottom edge survives.
Input: board = [["O","O"],["O","X"]] Output: [["O","O"],["O","X"]]
Every O touches the border, so nothing changes.
Input: board = [["X","X","X","X","X"],["X","O","O","X","X"],["X","X","O","X","X"],["X","X","O","O","O"]] Output: [["X","X","X","X","X"],["X","O","O","X","X"],["X","X","O","X","X"],["X","X","O","O","O"]]
The O cells wind down to the right edge, so the whole region survives.
Constraints
- m == len(board), n == len(board[i])
- 1 <= m, n <= 200
- board[i][j] is 'X' or 'O'
Approaches
- Baseline: ask each cell whether it can escape — time O((m · n)²), space O(m · n)
Follow-up
What if the board were too large for a call stack, or arrived one row at a time? Union-find with one extra "border" node handles both: join neighboring O cells, join border O cells to that node, and a cell is captured exactly when it is not in the border node's set.
Related problems
Start free on Cariara · Coding problems · System design studio
