Day 97 | Surrounded Regions

In this problem, you are given a 2-D grid. This grid contains "X" an "O" characters. If a group of O's is surrounded by X's on all 4 sides, it is considered to be surrounded. The goal of this problem is to change all surrounded regions of O's to X's. This is a pretty interesting problem that I learned a lot from.

The Approach

Initially, I thought of starting from all the O's on the board. I asked myself, how can I look for O's that are surrounded on the board. I initially started by thinking that I can traverse the board, look for O's, then perform a depth first search to see if it's group was surounded by X's. This approach felt a little complicated. The reason why is that you're not working with a singular cell. You are working with a group of cells. It's a lot more difficult to keep track if a whole group of cell's is surrounded rather than a single cell.

I actually found a different approach. What if instead you look for the group of cells that aren't surrounded. It's actually quite easy to find which cells these are. They are all the group of O's that are on the border of the grid. We can traverse all the borders, look for O's, perform a BFS on the cells surrounding those O's to mark those group of O's, then traverse the entire grid again to look for groups of O's that aren't marked. These groups that aren't marked are surrounded. We turn those to X's.

The Code

class Solution:
    def solve(self, board: List[List[str]]) -> None:
        ROWS, COLS = len(board), len(board[0])
        q = deque()
        for r in range(ROWS):
            for c in range(COLS):
                if (r == 0 or r == ROWS - 1 or c == 0 or c == COLS-1) and board[r][c] == "O":
                    q.append((r,c))
        while(q):
            for _ in range(len(q)):
                (r,c) = q.popleft()
                print(q)
                board[r][c] = "I"
                directions = [[1,0],[0,1],[-1,0],[0,-1]]
                for rowAdd, colAdd in directions:
                    new_r, new_c = r + rowAdd, c + colAdd
                    if new_r >= 0 and new_c >= 0 and new_r < ROWS and new_c < COLS and board[new_r][new_c] == "O":
                        print(board[new_r][new_c])
                        q.append((new_r,new_c))
        for r in range(ROWS):
            for c in range(COLS):
                if board[r][c] == "O":
                    board[r][c] = "X"
                if board[r][c] == "I":
                    board[r][c] = "O"
            
                                 

We start by creating a queue. We then loop through the entire grid. If the current cell is on the border, and is an O, we then add it to the queue. We then perform a BFS on those cells. We mark all the border group of O's with and 'I'. This way we keep track of the cells that are not surrounded. We then loop through the entire grid. If the current cell is an O, we change it to an X. If the current cell is an I, we change it back to and O.

Complexity Analysis

The time complexity of this solution is going to be O(m x n). The reason why is that the bfs method can only process each cell at most once. We then loop through the entire board another 2 times. This gives us something like O((m x n) + (m x n) + (m x n)) which just simplifies to m x n.

The space complexity is proportional to the size of the grid. This is because worst case scenario, the entire board is made up of O's which mean that every single cell would be in the queue at some point.