Table of Contents

# Surrounded Regions – LeetCode Solution Java , Python 3, Python 2 , C , C++, Best and Optimal Solutions , All you need.

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.

**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:Notice that an 'O' should not be flipped if: - It is on the border, or - It is adjacent to an 'O' that should not be flipped. The bottom 'O' is on the border, so it is not flipped. The other three 'O' form a surrounded region, so they are flipped.

**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'`

.

# C++ Surrounded Regions LeetCode Solution

```
``````
class Solution {
public:
void checkDown(vector<vector<char>>& b,vector<vector<bool>>& vis,int r,int c){
if(c < 0 || r < 0 || r >= b.size() || c >= b[0].size() || b[r][c] == 'X' || vis[r][c]) return;
vis[r][c] = 1;
checkDown(b,vis,r+1,c); // go down
checkDown(b,vis,r-1,c); // go up
checkDown(b,vis,r,c+1); // go right
checkDown(b,vis,r,c-1); // go left
return;
}
void solve(vector<vector<char>>& board) {
if(board.size() == 1) return ; // as no change can be done
if(board[0].size() == 1) return; // as no change can be done
int m = board.size();
int n = board[0].size();
vector<vector<bool>> vis(m,vector<bool>(n,0)); // make bool 2d array to store index of O that cannot be changed
// checking col 0 and n-1
for(int i=0;i<m;i++){
if(board[i][0] == 'O' && !vis[i][0]) checkDown(board, vis, i, 0); // calling for bfs to visit those nodes that cannot be changed
if(board[i][n-1] == 'O' && !vis[i][n-1]) checkDown(board, vis, i, n-1);
}
// checking row 0 and m-1
for(int i=0;i<n;i++){
if(board[0][i] == 'O' && !vis[0][i]) checkDown(board, vis, 0, i);
if(board[m-1][i] == 'O'&& !vis[m-1][i]) checkDown(board, vis, m-1, i);
}
// finally changing O to X if not visited
for(int i=0;i<m;i++){
for(int j=0;j<n;j++){
if(board[i][j] == 'O' && !vis[i][j]) board[i][j] = 'X';
}
}
}
};
```

# Java Surrounded Regions LeetCode Solution

```
```class Solution {

public void solve(char[][] board) {

```
int n = board.length;
int m = board[0].length;
for(int i=0;i<n;i++)
{
dfs(board,i,0,n,m);
dfs(board,i,m-1,n,m);
}
for(int i=0;i<m;i++)
{
dfs(board,0,i,n,m);
dfs(board,n-1,i,n,m);
}
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
{
if(board[i][j]=='#')
{
board[i][j]='O';
}
else if(board[i][j]=='O')
{
board[i][j]='X';
}
}
}
}
public void dfs(char[][] b,int i,int j,int n,int m)
{
if(i<0 || i>=n || j<0 || j>=m || b[i][j]=='X' || b[i][j]=='#' )
return;
b[i][j]='#';
dfs(b,i+1,j,n,m);
dfs(b,i,j+1,n,m);
dfs(b,i-1,j,n,m);
dfs(b,i,j-1,n,m);
}
```

}

# Python 3 Surrounded Regions LeetCode Solution

```
``````
class Solution:
def solve(self, board: List[List[str]]) -> None:
visit = set()
def dfs(r, c):
if r >= 0 and c >= 0 and r < len(board) and c < len(board[0]) and (r, c) not in visit and board[r][c] == "O":
visit.add((r, c))
dfs(r + 1, c)
dfs(r - 1, c)
dfs(r, c + 1)
dfs(r, c - 1)
for r in range(len(board)):
for c in range(len(board[0])):
if (r == 0 or c == 0 or r == len(board)-1 or c == len(board[0])-1) and board[r][c] == "O":
dfs(r, c)
for r in range(len(board)):
for c in range(len(board[0])):
board[r][c] = "X"
for r,c in visit:
board[r][c] = "O"
return board
```

Array-1180

String-562

Hash Table-412

Dynamic Programming-390

Math-368

Sorting-264

Greedy-257

Depth-First Search-256

Database-215

Breadth-First Search-200

Tree-195

Binary Search-191

Matrix-176

Binary Tree-160

Two Pointers-151

Bit Manipulation-140

Stack-133

Heap (Priority Queue)-117

Design-116

Graph-108

Simulation-103

Prefix Sum-96

Backtracking-92

Counting-86

Sliding Window-73

Linked List-69

Union Find-66

Ordered Set-48

Monotonic Stack-47

Recursion-43

Trie-41

Binary Search Tree-40

Divide and Conquer-40

Enumeration-39

Bitmask-37

Queue-33

Memoization-32

Topological Sort-31

Geometry-30

Segment Tree-27

Game Theory-24

Hash Function-24

Binary Indexed Tree-21

Interactive-18

Data Stream-17

String Matching-17

Rolling Hash-17

Shortest Path-16

Number Theory-16

Combinatorics-15

Randomized-12

Monotonic Queue-9

Iterator-9

Merge Sort-9

Concurrency-9

Doubly-Linked List-8

Brainteaser-8

Probability and Statistics-7

Quickselect-7

Bucket Sort-6

Suffix Array-6

Minimum Spanning Tree-5

Counting Sort-5

Shell-4

Line Sweep-4

Reservoir Sampling-4

Eulerian Circuit-3

Radix Sort-3

Strongly Connected Componen-t2

Rejection Sampling-2

Biconnected Component-1

## Leave a comment below