DSA problem
Surrounded Regions
Given an m x n matrix board containing 'X' and 'O', capture all regions that are 4-directionally surrounded by 'X'. A region is captured by flipping all 'O's into 'X's in that surrounded region. A region of 'O's is captured iff and only if it is NOT connected to any 'O' on the BORDER of the board.
The naive approach — scan each 'O' region, then check whether it touches the border — repeats work. A much cleaner inversion is: any 'O' connected to a border 'O' is SAFE, and every other 'O' is captured. So we start from the border and flood-fill outward.
The optimal algorithm is in two passes. First, run DFS from every 'O' on the four borders, marking the entire reachable 'O'-region as a temporary symbol like 'S' (safe). Second, scan the full board: any remaining 'O' is surrounded so flip it to 'X'; any 'S' is safe so revert it back to 'O'. The result is the captured board.
Time is O(m * n) because each cell is touched a constant number of times (border DFS plus final scan). Worst-case recursion depth is O(m * n) on a fully 'O'-board, so auxiliary space is O(m * n) for the stack. Using an iterative stack would not change the asymptotic space.
Examples
board = [["X","X","X","X"],["X","O","O","X"],["X","X","O","X"],["X","O","X","X"]][["X","X","X","X"],["X","X","X","X"],["X","X","X","X"],["X","O","X","X"]]board = [["X"]][["X"]]board = [["O","O"],["O","O"]][["O","O"],["O","O"]]Constraints
- m == board.length
- n == board[i].length
- 1 <= m, n <= 200
- board[i][j] is 'X' or 'O'.
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.