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.lengthn == board[i].length1 <= m, n <= 200board[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
