Solution For Surrounded Regions

Surrounded Regions problem on leetcode:

Given an m x n matrix board containing ‘X’ and ‘O’, flip all ‘O’s which are surrounded by ‘X’s to ‘X’.

A region is considered to be surrounded by ‘X’s if all the cells in the region that are in the border of the matrix are ‘X’s.

Example:
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:
Surrounded regions shouldn’t be on the border, which means that any ‘O’ on the border of the board are not flipped to ‘X’. Any ‘O’ that is not on the border and it is not connected to an ‘O’ from the border will be flipped to ‘X’. Two cells are connected if they are adjacent cells connected horizontally or vertically.

Approach:
1. We will be using a DFS traversal to find all the ‘O’s which are not surrounded by ‘X’s.
2. First, we initialize the borders of the matrix and add them to the queue. We won’t be changing any ‘O’ on the borders. If any ‘O’ is found on the borders, we can assume it is not surrounded by ‘X’s.
3. We traverse every cell in the matrix and if ‘O’ is found, we push it to the queue and mark it as ‘visited’ by changing it to ‘N’ (because it will now be surrounded by ‘X’s).
4. Now, we will run a DFS until the queue is empty. In the DFS function, for every ‘O’ present in the queue, we will mark it as ‘visited’ by changing it to ‘N’ (because it will now be surrounded by ‘X’s) and add its neighbouring cells to the queue.
5. After the DFS is completed, we iterate through the matrix again and change all ‘O’s to ‘X’s and all ‘N’s to ‘O’s.

Code:

class Solution {
public:
void solve(vector>& board) {
int m = board.size();
if(m==0) return;
int n = board[0].size();
queue> q;
// Adding elements on the borders to the queue
for(int i=0;i<m;i++){
if(board[i][0] == ‘O’) q.push(make_pair(i,0));
if(board[i][n-1] == ‘O’) q.push(make_pair(i,n-1));
}
for(int j=0;j curr = q.front();
q.pop();
int x = curr.first, y = curr.second;
if(x>=0 && x=0 && y<n && board[x][y]==’O’){
board[x][y] = ‘N’; // Marking all ‘O’ as ‘N’ as it is no longer surrounded by ‘X’
q.push(make_pair(x-1,y)); // Up
q.push(make_pair(x+1,y)); // Down
q.push(make_pair(x,y-1)); // Left
q.push(make_pair(x,y+1)); // Right
}
}
// Changing all ‘O’ to ‘X’ and all ‘N’ 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] == ‘N’) board[i][j] = ‘O’;
}
}
}
};

Time complexity: O(m*n) as we are iterating through every cell in the matrix.
Space complexity: O(m+n) as the maximum size of the queue can be m+n (for a boundary cell).

Step by Step Implementation For Surrounded Regions

class Solution {
    public void solve(char[][] board) {
        if (board == null || board.length == 0) {
            return;
        }
        int m = board.length;
        int n = board[0].length;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                // start from the edges and use dfs to mark all the connected 'O's as '#'
                if ((i == 0 || i == m - 1 || j == 0 || j == n - 1) && board[i][j] == 'O') {
                    dfs(board, i, j);
                }
            }
        }
        // flip all the 'O's to 'X's and all the '#'s to 'O's
        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 i, int j) {
        if (i < 0 || i >= board.length || j < 0 || j >= board[0].length || board[i][j] == 'X' || board[i][j] == '#') {
            return;
        }
        // mark the current cell as '#'
        board[i][j] = '#';
        // check all the adjacent cells
        dfs(board, i + 1, j);
        dfs(board, i - 1, j);
        dfs(board, i, j + 1);
        dfs(board, i, j - 1);
    }
}

class Solution:
    def solve(self, board: List[List[str]]) -> None:
        """
        Do not return anything, modify board in-place instead.
        """
        #Base case
        if not board:
            return 
        
        #Get the dimensions of the board
        rows = len(board)
        cols = len(board[0])
        
        #Create a visited 2D array to keep track of which cells have been visited
        visited = [[False for i in range(cols)] for j in range(rows)]
        
        #Do a DFS from every 'O' cell on the boundary of the board
        for i in range(rows):
            for j in range(cols):
                #If the current cell is 'O' and it's on the boundary of the board, do a DFS from that cell
                if board[i][j] == 'O' and (i == 0 or j == 0 or i == rows-1 or j == cols-1):
                    self.DFS(board, i, j, visited)
                    
        #After the DFS, every 'O' cell that was reachable from the boundary will be marked as visited
        #So, we can now go through the whole board again and change every 'O' cell to 'X' that isn't visited
        for i in range(rows):
            for j in range(cols):
                if board[i][j] == 'O' and not visited[i][j]:
                    board[i][j] = 'X'
                    
    def DFS(self, board, i, j, visited):
        #Mark the current cell as visited
        visited[i][j] = True
        
        #Get the dimensions of the board
        rows = len(board)
        cols = len(board[0])
        
        #Recursively call DFS on all unvisited 'O' cells reachable from the current cell
        #(i.e. all 'O' cells that are adjacent to the current cell)
        if i > 0 and board[i-1][j] == 'O' and not visited[i-1][j]:
            self.DFS(board, i-1, j, visited)
        if i < rows-1 and board[i+1][j] == 'O' and not visited[i+1][j]:
            self.DFS(board, i+1, j, visited)
        if j > 0 and board[i][j-1] == 'O' and not visited[i][j-1]:
            self.DFS(board, i, j-1, visited)
        if j < cols-1 and board[i][j+1] == 'O' and not visited[i][j+1]:
            self.DFS(board, i, j+1, visited)

Given a 2D board containing 'X' and 'O' (the letter O), capture all regions surrounded by 'X'.

A region is captured by flipping all 'O's into 'X's in that surrounded region.

For example,
X X X X
X O O X
X X O X
X O X X
After running your function, the board should be:

X X X X
X X X X
X X X X
X O X X

class Solution {
public:
    void solve(vector>& board) {
        
        //check if the first and last row have any 'O's. If they do, change them and all their connected 'O's to '*'s
        for(int i = 0; i < board.size(); i++){
            for(int j = 0; j < board[0].size(); j++){
                //if we find an 'O' on the first or last row
                if((i == 0 || i == board.size() - 1) && board[i][j] == 'O'){
                    //change it to a '*'
                    board[i][j] = '*';
                    //call our helper function on this 'O' to change all its connected 'O's to '*'s
                    flip(board, i, j);
                }
            }
        }
        
        //check if the first and last column have any 'O's. If they do, change them and all their connected 'O's to '*'s
        for(int i = 0; i < board.size(); i++){
            for(int j = 0; j < board[0].size(); j++){
                //if we find an 'O' on the first or last column
                if((j == 0 || j == board[0].size() - 1) && board[i][j] == 'O'){
                    //change it to a '*'
                    board[i][j] = '*';
                    //call our helper function on this 'O' to change all its connected 'O's to '*'s
                    flip(board, i, j);
                }
            }
        }
        
        //go through the entire board and change all 'O's to 'X's and all '*'s back to 'O's
        for(int i = 0; i < board.size(); i++){
            for(int j = 0; j < board[0].size(); j++){
                if(board[i][j] == 'O'){
                    board[i][j] = 'X';
                }
                else if(board[i][j] == '*'){
                    board[i][j] = 'O';
                }
            }
        }
    }
    
    //a helper function that takes in the board and the coordinates of an 'O'. 
    //It then changes all connected 'O's to '*'s
    void flip(vector>& board, int i, int j){
        //if we are out of bounds or if the current element is not an 'O', return
        if(i < 0 || i >= board.size() || j < 0 || j >= board[0].size() || board[i][j] != 'O'){
            return;
        }
        
        //change the current element to a '*'
        board[i][j] = '*';
        
        //call our helper function on all adjacent elements
        flip(board, i + 1, j);
        flip(board, i - 1, j);
        flip(board, i, j + 1);
        flip(board, i, j - 1);
    }
};

class Solution { 
    public void Solve(char[][] board) {
        if (board == null || board.Length == 0) return;
        int m = board.Length, n = board[0].Length;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                // only consider 'O' on the border
                bool isEdge = i == 0 || j == 0 || i == m - 1 || j == n - 1;
                if (isEdge && 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] == 'O') {
                    board[i][j] = 'X';
                }
                if (board[i][j] == '#') {
                    board[i][j] = 'O';
                }
            }
        }
    }
    private void DFS(char[][] board, int i, int j) {
        if (i < 0 || j < 0 || i >= board.Length || j >= board[0].Length || board[i][j] == 'X' || board[i][j] == '#') return;
        board[i][j] = '#';
        DFS(board, i - 1, j);
        DFS(board, i + 1, j);
        DFS(board, i, j - 1);
        DFS(board, i, j + 1);
    }
}