# Surrounded Regions
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/surrounded-regions)
Canonical: https://scaleengineer.com/dsa/problems/surrounded-regions
**Algorithms:** [Depth-First Search](https://scaleengineer.com/algorithms/depth-first-search), [Breadth-First Search](https://scaleengineer.com/algorithms/breadth-first-search), [Union Find](https://scaleengineer.com/algorithms/union-find)
**Data structures:** Array, Matrix
**Companies:** [Flipkart](https://scaleengineer.com/companies/flipkart), [Nutanix](https://scaleengineer.com/companies/nutanix), [TikTok](https://scaleengineer.com/companies/tiktok), [Arcesium](https://scaleengineer.com/companies/arcesium), [Urban Company](https://scaleengineer.com/companies/urban-company)
---
## Problem
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`.

To capture a **surrounded region**, replace all `'O'`s with `'X'`s **in-place** within the original board. You do not need to return anything.

**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:**

![](https://assets.glich.co/dsa/surrounded-regions/image0.jpg) 

In the above diagram, the bottom region is not captured because it is on the edge of the board and cannot be surrounded.

**Example 2:**

**Input:** board = \[\["X"\]\]

**Output:** \[\["X"\]\]

**Constraints:**

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

# Approaches
## Naive Traversal for Each 'O'
This brute-force approach iterates through every cell of the board. For each cell containing an 'O', it initiates a completely new and independent graph traversal (like Breadth-First Search or Depth-First Search) to determine if the region of 'O's it belongs to is surrounded by 'X's. This check is performed from scratch for each 'O', leading to an extremely high number of redundant computations.
**Time:** O((m*n)^2) · **Space:** O(m*n)
**Pros:** Conceptually simple to understand as it directly translates the problem statement: for each 'O', check if it's surrounded.
**Cons:** Extremely inefficient due to massive redundant computations. The same region of 'O's will be traversed multiple times, once for each 'O' within it.; High time complexity makes it impractical for larger boards.; Requires significant extra space for the temporary `visited` matrix in each check.
### Explanation
The fundamental idea is to check every single 'O' individually. For an 'O' at position `(r, c)`, we ask the question: "Is the region this 'O' belongs to completely surrounded?" To answer this, we perform a search that explores all reachable 'O's starting from `(r, c)`. During this search, we check if we ever touch the board's boundary. If we do, the region is not surrounded. If we explore the entire region without touching a boundary, it is surrounded. The critical flaw is that if a region has 50 'O's, we will perform this expensive check 50 separate times, each time re-exploring the entire 50-'O' region.
### Algorithm
1.  Create a helper function, `isRegionSurrounded(row, col, board)`, that determines if the 'O' at `(row, col)` belongs to a surrounded region.
2.  Inside this helper function:
    *   Initialize a new temporary `visited` matrix for each call.
    *   Start a traversal (BFS or DFS) from `(row, col)`.
    *   Explore all connected 'O's, marking them in the temporary `visited` matrix.
    *   If any 'O' encountered during the traversal is on the border of the board, the region is not surrounded. The function returns `false`.
    *   If the traversal completes without finding any border 'O's, the region is surrounded. The function returns `true`.
3.  In the main function, iterate through every cell `(r, c)` of the board.
4.  If `board[r][c]` is an 'O', call `isRegionSurrounded(r, c, board)`.
5.  This approach is flawed because you cannot flip the 'O's immediately, as it would affect subsequent checks. You would need to store the coordinates of all 'O's that are part of surrounded regions and then flip them in a final pass, adding more complexity and space.

## Group and Flip Traversal
A more optimized approach is to iterate through the board and, upon finding an unvisited 'O', perform a single traversal to identify its entire connected region. During this traversal, we check if the region is connected to a border. If not, we flip all 'O's in that region to 'X's. A global `visited` matrix is used to ensure each 'O' is processed only once.
**Time:** O(m*n) · **Space:** O(m*n)
**Pros:** Correct and much more efficient than the naive approach.; Guarantees that each cell is processed only once, leading to a linear time complexity.
**Cons:** Requires extra space O(m*n) not just for the `visited` matrix but also to store the coordinates of each region before deciding whether to flip.; Can be slightly less performant in practice than the border-search approach as it may still traverse large internal regions that end up not being flipped.
### Explanation
This method improves upon the naive approach by ensuring that each 'O' is visited only once. We use a `visited` matrix to keep track of cells we've already considered. When we find an 'O' that hasn't been visited, we launch a search (like BFS) to find all 'O's in its connected component. We gather all these 'O's into a temporary list and simultaneously check if any of them are on the boundary. Once the entire region has been explored, we make a decision. If no boundary cell was found, we iterate through our temporary list and flip all the collected 'O's to 'X's. Otherwise, we discard the list and move on, leaving the region as is. This prevents the redundant traversals of the naive method.

```java
class Solution {
    public void solve(char[][] board) {
        if (board == null || board.length == 0) {
            return;
        }
        int m = board.length;
        int n = board[0].length;
        boolean[][] visited = new boolean[m][n];

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (board[i][j] == 'O' && !visited[i][j]) {
                    List<int[]> regionCells = new ArrayList<>();
                    Queue<int[]> queue = new LinkedList<>();
                    boolean isSurrounded = true;

                    queue.offer(new int[]{i, j});
                    visited[i][j] = true;

                    while (!queue.isEmpty()) {
                        int[] cell = queue.poll();
                        int r = cell[0];
                        int c = cell[1];
                        regionCells.add(cell);

                        if (r == 0 || r == m - 1 || c == 0 || c == n - 1) {
                            isSurrounded = false;
                        }

                        int[] dr = {-1, 1, 0, 0};
                        int[] dc = {0, 0, -1, 1};

                        for (int k = 0; k < 4; k++) {
                            int nr = r + dr[k];
                            int nc = c + dc[k];

                            if (nr >= 0 && nr < m && nc >= 0 && nc < n &&
                                board[nr][nc] == 'O' && !visited[nr][nc]) {
                                visited[nr][nc] = true;
                                queue.offer(new int[]{nr, nc});
                            }
                        }
                    }

                    if (isSurrounded) {
                        for (int[] cell : regionCells) {
                            board[cell[0]][cell[1]] = 'X';
                        }
                    }
                }
            }
        }
    }
}
```
### Algorithm
1.  Initialize an `m x n` `visited` boolean matrix with all values set to `false`.
2.  Iterate through each cell `(r, c)` of the board from `(0, 0)` to `(m-1, n-1)`.
3.  If `board[r][c]` is 'O' and `visited[r][c]` is `false`, it signifies the start of a new, unexplored region.
4.  Begin a traversal (e.g., BFS) from `(r, c)`.
5.  During the traversal, maintain a list to store the coordinates of all 'O's in the current region and a boolean flag, `is_surrounded`, initialized to `true`.
6.  For every 'O' visited, mark it as `true` in the `visited` matrix, add its coordinates to the list, and check if it's on a border. If it is, set `is_surrounded` to `false`.
7.  After the traversal for the region is complete, check the `is_surrounded` flag.
8.  If `is_surrounded` is `true`, iterate through the stored coordinates for the region and flip the corresponding 'O's on the board to 'X's.

## Border Search (DFS/BFS)
This is the most efficient and clever approach. The core insight is that any 'O' that is on the border, or is connected to an 'O' on the border, cannot be captured. All other 'O's are by definition surrounded. The algorithm works by "working backwards" from the borders to find all the 'O's that *shouldn't* be flipped.
**Time:** O(m*n) · **Space:** O(m*n)
**Pros:** Most efficient approach with O(m*n) time complexity.; Elegant logic that simplifies the problem.; Space efficient, as it can modify the board in-place (using a temporary marker) and the primary space usage is the recursion stack or an explicit queue/stack for traversal.
**Cons:** The logic of "working backwards" from the borders might be slightly less intuitive at first glance.; Requires modifying the input board with a temporary marker, which might not be permissible in all problem variations.
### Explanation
Instead of trying to identify surrounded regions, we identify all *un-surrounded* regions. An 'O' is un-surrounded if it's on the border or can reach a border 'O' through a path of other 'O's. The algorithm first traverses the grid starting from every 'O' on the edges. Any 'O' that can be reached from an edge 'O' is considered "safe". We mark these safe 'O's, for instance, by changing them to a temporary character like '#'. After this marking process is complete, we perform a final sweep of the entire board. Any 'O' that was not marked (i.e., is still 'O') must be unreachable from the border and is therefore surrounded; we flip it to 'X'. Any cell we marked as '#' is a safe 'O' that should be preserved, so we flip it back to 'O'. This approach is highly efficient because the initial traversals only explore the "safe" regions, which are often a smaller subset of the board.

```java
class Solution {
    public void solve(char[][] board) {
        if (board == null || board.length == 0) {
            return;
        }
        int m = board.length;
        int n = board[0].length;

        // 1. Mark 'O's on the border and their connected 'O's as safe ('#')
        for (int i = 0; i < m; i++) {
            if (board[i][0] == 'O') {
                dfs(board, i, 0);
            }
            if (board[i][n - 1] == 'O') {
                dfs(board, i, n - 1);
            }
        }
        for (int j = 0; j < n; j++) {
            if (board[0][j] == 'O') {
                dfs(board, 0, j);
            }
            if (board[m - 1][j] == 'O') {
                dfs(board, m - 1, j);
            }
        }

        // 2. Flip remaining 'O's to 'X' and safe '#' back to 'O'
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (board[i][j] == 'O') {
                    board[i][j] = 'X';
                } else if (board[i][j] == '#') {
                    board[i][j] = 'O';
                }
            }
        }
    }

    private void dfs(char[][] board, int r, int c) {
        int m = board.length;
        int n = board[0].length;

        if (r < 0 || r >= m || c < 0 || c >= n || board[r][c] != 'O') {
            return;
        }

        board[r][c] = '#'; // Mark as safe

        dfs(board, r + 1, c);
        dfs(board, r - 1, c);
        dfs(board, r, c + 1);
        dfs(board, r, c - 1);
    }
}
```
### Algorithm
1.  **Marking Phase:**
    *   Iterate through all cells on the four borders of the grid.
    *   If a border cell `(r, c)` contains an 'O', it is part of an un-surrounded region.
    *   Start a traversal (DFS or BFS) from this border 'O'.
    *   In the traversal, find all connected 'O's and change them to a temporary marker (e.g., '#') to mark them as "safe".
2.  **Flipping Phase:**
    *   After all border 'O's and their connected components are marked, iterate through the entire grid again.
    *   For each cell `(r, c)`:
        *   If `board[r][c] == 'O'`, it means this 'O' was not reachable from any border and is therefore surrounded. Flip it to 'X'.
        *   If `board[r][c] == '#'`, it's a "safe" 'O'. Revert it back to 'O'.

# Solutions
### CSharp

```csharp
using System ; using System.Collections.Generic ; public class Solution { private static readonly int [,] directions = new int [ 4 , 2 ] { { 1 , 0 }, { 0 , 1 }, { - 1 , 0 }, { 0 , - 1 } }; public void Solve ( char [][] board ) { var lenI = board . Length ; var lenJ = lenI == 0 ? 0 : board [ 0 ]. Length ; for ( var i = 0 ; i < lenI ; ++ i ) { for ( var j = 0 ; j < lenJ ; ++ j ) { if ( board [ i ][ j ] == 'O' ) { var marked = new List < Tuple < int , int >>(); marked . Add ( Tuple . Create ( i , j )); board [ i ][ j ] = 'M' ; bool escaped = false ; for ( var m = 0 ; m < marked . Count ; ++ m ) { for ( var k = 0 ; k < 4 ; ++ k ) { var newI = marked [ m ]. Item1 + directions [ k , 0 ]; var newJ = marked [ m ]. Item2 + directions [ k , 1 ]; if ( newI < 0 || newI >= lenI || newJ < 0 || newJ >= lenJ ) { escaped = true ; } else if ( board [ newI ][ newJ ] == 'O' ) { board [ newI ][ newJ ] = 'M' ; marked . Add ( Tuple . Create ( newI , newJ )); } } } if (! escaped ) { foreach ( var item in marked ) { board [ item . Item1 ][ item . Item2 ] = 'X' ; } } } } } for ( var i = 0 ; i < lenI ; ++ i ) { for ( var j = 0 ; j < lenJ ; ++ j ) { if ( board [ i ][ j ] == 'M' ) { board [ i ][ j ] = 'O' ; } } } } }
```

### Java

```java
class Solution {
private
  char[][] board;
private
  int m;
private
  int n;
public
  void solve(char[][] board) {
    m = board.length;
    n = board[0].length;
    this.board = board;
    for (int i = 0; i < m; ++i) {
      for (int j = 0; j < n; ++j) {
        if ((i == 0 || i == m - 1 || j == 0 || j == n - 1) &&
            board[i][j] == 'O') {
          dfs(i, j);
        }
      }
    }
    for (int i = 0; i < m; ++i) {
      for (int j = 0; j < n; ++j) {
        if (board[i][j] == '.') {
          board[i][j] = 'O';
        } else if (board[i][j] == 'O') {
          board[i][j] = 'X';
        }
      }
    }
  }
private
  void dfs(int i, int j) {
    board[i][j] = '.';
    int[] dirs = {-1, 0, 1, 0, -1};
    for (int k = 0; k < 4; ++k) {
      int x = i + dirs[k];
      int y = j + dirs[k + 1];
      if (x >= 0 && x < m && y >= 0 && y < n && board[x][y] == 'O') {
        dfs(x, y);
      }
    }
  }
}

```

### CPP

```cpp
class Solution {
public:
  void solve(vector<vector<char>> &board) {
    int m = board.size(), n = board[0].size();
    for (int i = 0; i < m; ++i)
      for (int j = 0; j < n; ++j)
        if ((i == 0 || i == m - 1 || j == 0 || j == n - 1) &&
            board[i][j] == 'O')
          dfs(board, i, j);
    for (int i = 0; i < m; ++i) {
      for (int j = 0; j < n; ++j) {
        if (board[i][j] == '.')
          board[i][j] = 'O';
        else if (board[i][j] == 'O')
          board[i][j] = 'X';
      }
    }
  }
  void dfs(vector<vector<char>> &board, int i, int j) {
    board[i][j] = '.';
    vector<int> dirs = {-1, 0, 1, 0, -1};
    for (int k = 0; k < 4; ++k) {
      int x = i + dirs[k], y = j + dirs[k + 1];
      if (x >= 0 && x < board.size() && y >= 0 && y < board[0].size() &&
          board[x][y] == 'O')
        dfs(board, x, y);
    }
  }
};

```

### Python

```python
class Solution:
    def solve(self, board: List[List[str]]) -> None: """ Do not return anything, modify board in-place instead. """ def dfs(i, j): board[i][j] = '.' for a, b in [[0, - 1], [0, 1], [1, 0], [- 1, 0]]: x, y = i + a, j + b if 0 <= x < m and 0 <= y < n and board[x][y] == 'O': dfs(x, y) m, n = len(board), len(board[0]) for i in range(m): for j in range(n): if board[i][j] == 'O' and (i == 0 or i == m - 1 or j == 0 or j == n - 1): dfs(i, j) for i in range(m): for j in range(n): if board[i][j] == 'O': board[i][j] = 'X' elif board[i][j] == '.': board[i][j] = 'O'

```