[Top Interview 150] 130. Surrounded Regions

Solution)

class Solution:
    def solve(self, board: List[List[str]]) -> None:
        # rows and cols are the number of rows and columns of board
        # visit is a set of positions of "O" that have been visited before
        rows, cols, visit = len(board), len(board[0]), set()

        # Modifies board using BFS method
        def bfs(r, c):
            # A list of directions including itself
            directions = [[0,0], [0,1], [0,-1], [1,0], [-1,0]]

            # q is a deque that is used to access children elements
            # curr saves positions of "O" in the current region
            q, curr = collections.deque(), set()

            # capturable lets us know if the current region is capturable
            capturable = True

            q.append((r,c))

            # Steps of BFSing
            while q:
                row, col = q.popleft()

                # Check itself and 4 touching elements
                for dr,dc in directions:
                    r, c = row+dr, col+dc

                    if (r in range(rows)
                    and c in range(cols)
                    and board[r][c] == "O"
                    and (r,c) not in visit):
                        # If the current "O" is on border
                        # current region is not capturable
                        if r in (0, rows-1) or c in (0, cols-1):
                            capturable = False

                        q.append((r,c))
                        curr.add((r,c))
                        visit.add((r,c))
            
            # If the current region is capturable flip "O" to "X"
            if capturable:
                for row, col in curr:
                    board[row][col] = "X"
                        
        # Iterate the entire unvisited elements 
        for r in range(rows):
            for c in range(cols):
                if board[r][c] == "O" and (r,c) not in visit:
                    bfs(r, c)

 
Problem: LeetCode
 
Time Complexity: O(n*m)
Space Complexity: O(n*m)
*n, m = len(board), len(board[0])
 

Explanation)

We'll use BFS method to find the proper region of "O" and flip them to "X".
 
1) Find the region of "O"s and save their positions regardless of whether the region is capturable or not.
2) If the region is capaturable (meaning all of the elements of the region are not on the borders), we flip the "O"s.
 

1. Initialization)

Variable rows and cols are the actual numbers of rows and columns of board.
 
Variable visit is a set that will save the positions of the elements that were already visited while iterating. We do this because there will always be a case where the same elements will be visited multiple times. This set allows us to avoid that.
 

def solve(self, board: List[List[str]]) -> None:
        # 1. Initialization
        rows, cols, visit = len(board), len(board[0]), set()

 

2. Iterate board)

To find the regions, we'll iterate all the elements in board.
 
If the element is "O" and not visited yet, we'll do BFS starting from the current position. Our helper function will not only discover the entire region but also flip "O"s to "X"s if capturable.
 

def solve(self, board: List[List[str]]) -> None:
        # 1. Initialization
        rows, cols, visit = len(board), len(board[0]), set()

        # We'll look into it later ;)
        def bfs(r, c):
            pass

        # 2. Iterate board
        for r in range(rows):
            for c in range(cols):
                if board[r][c] == "O" and (r,c) not in visit:
                    bfs(r, c)

 

3. Helper function initialization)

Keep in mind that our helper function will discover the entire region and flip to "X"s if capturable.
 
Variables:

• directions allows us to check itself and 4 touching elements
• q will save positions of the root elements which allow us to access their children elements (4 touching elements).
• curr will save the positions of "O" elements of the current region.
• capturable is a flag that checks whether the current region should be flipped into "X".

 
Append the current position (r,c) to q to start BFSing.
 

def solve(self, board: List[List[str]]) -> None:
        # 1. Initialization
        rows, cols, visit = len(board), len(board[0]), set()

        def bfs(r, c):
            # 3. Helper function initialization
            directions = [[0,0], [0,1], [0,-1], [1,0], [-1,0]]
            q, curr = collections.deque(), set()
            capturable = True

            q.append((r,c))

        # 2. Iterate board
        for r in range(rows):
            for c in range(cols):
                if board[r][c] == "O" and (r,c) not in visit:
                    bfs(r, c)

 

4. BFS from the current (r,c)

Now we'll BFS from the current position (r,c).
 
We do fundamentally the same thing.
1) Get the root elements
2) Retrieve their children elements (4 touching elements)
3) If the children elements meet the conditions, append them back to deque to continue BFSing
 
A few more things to do in this step are
1) to check if the elements are in the border
2) to add the positions to curr and visit.
 
By adding positions to curr, we'll get the entire positions of the elements in the current region.
By adding positions to visit, we'll later use this to prevent checking the elements that were already visited again.
 

def solve(self, board: List[List[str]]) -> None:
        # 1. Initialization
        rows, cols, visit = len(board), len(board[0]), set()

        def bfs(r, c):
            # 3. Helper function initialization
            directions = [[0,0], [0,1], [0,-1], [1,0], [-1,0]]
            q, curr = collections.deque(), set()
            capturable = True

            q.append((r,c))

            # 4. BFS from the current (r,c)
            while q:
                row, col = q.popleft()

                for dr,dc in directions:
                    r, c = row+dr, col+dc

                    if (r in range(rows)
                    and c in range(cols)
                    and board[r][c] == "O"
                    and (r,c) not in visit):
                        if r in (0, rows-1) or c in (0, cols-1):
                            capturable = False

                        q.append((r,c))
                        curr.add((r,c))
                        visit.add((r,c))
                        
        # 2. Iterate board
        for r in range(rows):
            for c in range(cols):
                if board[r][c] == "O" and (r,c) not in visit:
                    bfs(r, c)

 

5. Flip "O"s)

After step 4, we have positions of all the elements of the current region. Now let's see if the current region is capturable.
 
Conveniently, we have a boolean variable that makes this easy. Simply, if capturable is True, we'll flip the elements into "X"s.
 
Since we saved the positions of the elements of the region in curr, we'll use that information to flip "O"s to "X"s.
 

def solve(self, board: List[List[str]]) -> None:
        # 1. Initialization
        rows, cols, visit = len(board), len(board[0]), set()

        def bfs(r, c):
            # 3. Helper function initialization
            directions = [[0,0], [0,1], [0,-1], [1,0], [-1,0]]
            q, curr = collections.deque(), set()
            capturable = True

            q.append((r,c))

            # 4. BFS from the current (r,c)
            while q:
                row, col = q.popleft()

                for dr,dc in directions:
                    r, c = row+dr, col+dc

                    if (r in range(rows)
                    and c in range(cols)
                    and board[r][c] == "O"
                    and (r,c) not in visit):
                        if r in (0, rows-1) or c in (0, cols-1):
                            capturable = False

                        q.append((r,c))
                        curr.add((r,c))
                        visit.add((r,c))
            
            # 5. Flip "O"s
            if capturable:
                for row, col in curr:
                    board[row][col] = "X"
                        
        # 2. Iterate board
        for r in range(rows):
            for c in range(cols):
                if board[r][c] == "O" and (r,c) not in visit:
                    bfs(r, c)

---

 
 
 
It's a similar question to the previous one but with a few more steps. I also think this solution isn't so efficient. So I'll try different approaches for other questions.
 
Have a wonderful day.