118. Surrounded Regions

MediumGraph

You are given an m x n matrix board containing letters 'X' and 'O', capture regions that are surrounded: - Connect: A cell is connected to adjacent cells horizontally or vertically. - Region: To form a region connect every 'O' cell. - Surround: The region is surrounded with 'X' cells if you can connect the region with 'X' cells and none of the region cells are on the edge of the board. A surrounded region is captured by replacing all 'O's with 'X's in the input matrix board.

Examples

Example 1

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"]]

Explanation: The O's at (1,1), (1,2) and (2,2) form a region that never touches the edge, so they are captured and become X. The O at (3,1) lies on the bottom edge, so it survives.

Example 2

Input: board = [["X"]]

Output: [["X"]]

Explanation: There are no O's, so nothing changes.

Example 3

Input: board = [["O","O"],["O","O"]]

Output: [["O","O"],["O","O"]]

Explanation: Every O is on the edge of the board, so none of them can be surrounded, and the board stays the same.

Constraints

m == board.length
n == board[i].length
1 <= m, n <= 200
board[i][j] is 'X' or 'O'.

How to solve Surrounded Regions: approach and complexity

Flood Fill from the Borders: time, space.

An 'O' survives only if it can reach the border. So instead of hunting for surrounded regions, flood-fill from every border 'O' to mark all connected 'O's as safe; then flip everything else ('O' → 'X') and restore the safe ones.

Watch it run step by step