Leetcode 130 : Surrounded Regions

Problem Statement :

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.

Test Cases :

Constraints :

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

Approach :

The main thing to note that, we can't simply flip all O to X. Surrounded regions should not 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' on the border will be flipped to 'X'. Two cells are connected if they are adjacent cells connected horizontally or vertically.

So we are only concerned with those O that are on the 4 boundary ie either on the top row, bottom row, left most column or right most column.

That makes us to first find those O that are on the boundaries of the matrix and do a DFS/BFS from that O to find other O which are connected. We then normally traverse the matrix and change only those O to X which does not have any connection with these O.

For example :

X O X
X O X
X O X

Consider this example, here we are having O on the top most. So we find the cell with the O on top most and do either a DFS or BFS. While doing the search we will be temporarily changing O to any other character say '+'.
So after DFS/BFS, the resulting matrix will look as :

X + X
X + X
X + X

Now we do a normal matrix traversal and if we see a O in the matrix it is converted back to O, if we see a '+', it means they are violating the rule to be flipped to X, so we keep it as O. So the answer for the above example will be simply :

X O X
X O X
X O X

Now consider another example :
X X X X
X O O X
X X O X
X O X X

We check for those O that are on the boundary. There is only 1 O that is on the boundary which is at the bottom row (3, 1). We do a DFS/BFS and temporarily changing it as '+'.

X X X X
X O O X
X X O X
X + X X

Now as told earlier we do a normal matrix traversal and see if there is any O, if O's are present then flip it into X. If we see a '+', then keep it as a O.

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

Code :

DFS Approach

class Solution {
    public void solve(char[][] board) {
        if (board == null || board.length == 0)
            return;
        if (board.length < 3 || board[0].length < 3)
            return;
        int row = board.length;
        int col = board[0].length;
        for (int i=0; i<row; i++) {
            if (board[i][0] == 'O') {
                dfs(board, i, 0);
            }
            if (board[i][col - 1] == 'O') {
                dfs(board, i, col-1);
            }
        }
        for (int j=0; j<col; j++) {
            if (board[0][j] == 'O') {
                dfs(board, 0, j);
            }
            if (board[row-1][j] == 'O') {
                dfs(board, row-1, j);
            }
        }
        for (int i=0; i<row; i++) {
            for (int j=0; j<col; j++) {
                if (board[i][j] == '+') {
                    board[i][j] = 'O';
                }
                else if (board[i][j] == 'O') {
                    board[i][j] = 'X';
                }
            }
        }
    }

    public void dfs(char [][] board, int i, int j) {
        if (i < 0 || j < 0 || i >= board.length || j >= board[0].length || board[i][j] != 'O')
            return;
        board[i][j] = '+';
        dfs(board, i+1, j);
        dfs(board, i-1, j);
        dfs(board, i, j-1);
        dfs(board, i, j+1);
    }
}

BFS Approach

class Solution {
    public void solve(char[][] board) {
        if (board == null || board.length == 0)
            return;
        int row = board.length;
        int col = board[0].length;
        Queue<int[]> queue = new LinkedList<>();
        // add all the edge on top left right botom to queue
       for (int i=0; i<row; i++) {
           if (board[i][0] == 'O') {
               board[i][0] = '+';
               queue.offer(new int []{i, 0});
           }
           if (board[i][col - 1] == 'O') {
               board[i][col - 1] = '+';
               queue.offer(new int []{i, col - 1});
           }
       }
        for (int i=0; i<col; i++) {
            if (board[0][i] == 'O') {
                board[0][i] = '+';
                queue.offer(new int [] {0, i});
            }
            if (board[row - 1][i] == 'O') {
                board[row - 1][i] = '+';
                queue.offer(new int [] {row - 1, i});
            }
        }
        bfs(queue, row, col, board);
        for (int i=0; i<row; i++) {
            for (int j=0; j<col; j++) {
                if (board[i][j] == '+') {
                    board[i][j] = 'O';
                }
                else if (board[i][j] == 'O') {
                    board[i][j] = 'X';
                }
            }
        }

    }

    public void bfs(Queue<int[]> queue, int row, int col, char [][] board) {
        final int [][] directions = new int [][]{{0, 1}, {1, 0}, {-1, 0}, {0, -1}};
        while (!queue.isEmpty()) {
            int [] currentPos = queue.poll();
            int x = currentPos[0];
            int y = currentPos[1];
            for (int [] dir : directions) {
                int newX = x + dir[0];
                int newY = y + dir[1];
                if (newX < 0 || newY < 0 || newX >= row || newY >= col || board[newX][newY] != 'O')
                    continue;
                board[newX][newY] = '+';
                queue.offer(new int [] {newX, newY});
            }
        }
    }
}

Time complexity and Space Complexity :

Time complexity = O(row * col)
Space Complexity = O(row * col)

Rohithv07 / LeetCode

LeetCode problems that are solved.

LeetCode

LeetCode problems that are solved.

• take the bit of the ith(from right) digit:

  bit = (mask >> i) & 1;

• set the ith digit to 1: mask = mask | (1 << i);

• set the ith digit to 0: mask = mask & (~(1 << i));

View on GitHub

Comments

[Tuba Inam]

I found that solution is very popular and helpful: youtu.be/kmsWQKSwbnw