Surrounded Regions

Explanation & Solution

Description

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. An 'O' on the border of the board (or connected to a border 'O') is not surrounded and should not be flipped.

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' at position (3,1) is on the border and is not surrounded. The 'O's at (1,1), (1,2), and (2,2) are surrounded by 'X' on all sides, so they are captured and flipped to 'X'.

Constraints

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

Approach

Graphs pattern

1. Identify Safe Cells from the Border

Iterate along all four borders of the board
For every 'O' found on a border, start a DFS to mark it and all connected 'O's as safe ('S')
These cells are connected to the edge and therefore cannot be surrounded

2. DFS to Mark Connected Regions

From each border 'O', recursively visit all 4-directional neighbors
If a neighbor is 'O', mark it as 'S' and continue exploring
Stop when out of bounds or the cell is not 'O'

3. Capture Surrounded Regions

After all border-connected 'O's are marked as 'S', scan the entire board
Any remaining 'O' is fully surrounded — flip it to 'X'
Any 'S' is a safe cell — restore it back to 'O'

4. Return the Modified Board

The board is modified in place and returned
All surrounded regions have been captured while border-connected regions remain intact

Key Insight

Instead of trying to determine which 'O' regions are surrounded (which is harder), we flip the problem: find all 'O's that are not surrounded by starting from the borders
Everything left over must be surrounded — this is a classic boundary DFS technique

Time

O(m × n)each cell is visited at most twice

Space

O(m × n)recursion stack in the worst case

Visualization

Input:

DFS Traversal4×4 grid

output—

Press play to start dfs traversal

CurrentQueuedVisitedSource

28 steps

Solution Code

Walls and Gates

Pacific Atlantic Water Flow