Graphs · 117Medium
Surrounded Regions
Given an m x n board of 'X' and 'O', capture every region of 'O' that is completely surrounded by 'X' by flipping those cells to 'X'. A region touching the border is never captured.
Constraints
- m == board.length, n == board[i].length
- 1 <= m, n <= 200
- board[i][j] is 'X' or 'O'.
Examples
solve([["X","X","X"],["X","O","X"],["X","X","X"]]) -> the O becomes X solve([["O"]]) -> [["O"]] // touches the border, so it survives solve([["X"]]) -> [["X"]] // no O to capture solve([["X","X"],["X","O"]]) -> unchanged // the O is on the border solve([["O","O"],["O","O"]]) -> unchanged // every cell is border solve([["X","O","X"],["X","O","X"],["X","X","X"]]) -> unchanged // reaches the top border
Edge cases
- Any region connected to the border survives, however large.
- A 1x1 board is entirely border.
Show the target complexity (spoiler)
- Naive
- Checking each region for border contact separately re-walks the same cells
- Target
- O(m * n) time — invert the problem: flood-fill from every 'O' ON the border to mark survivors, then flip all unmarked 'O' cells.
Solve it
By hand, in your editor. The runner checks answers and timing.
git clone https://github.com/sarmadkung/optimal-round cd optimal-round # open problems/08-graphs/117-surrounded-regions.js ./practice c 117