Capture Regions on Board | InterviewBit | Solution Explained

I explain the solution to the problem Capture Regions on Board in detail, along with visuals and annotated code in Python3.

0. Capture Regions on Board: Problem Discussion

0.0. IO Format

• input:
  • a matrix of Xs and Os.
• output:
  • the same matrix (in-place changes) where all the Os that are surrounded get converted to X
• condition:
  • Os being surrounded means that they don’t have a connection from any of the borders. Look at the example below to understand better.

0.1. Examples

In the case above, the O marked in red gets converted to X, since it has no way of escape. On the other hands, all the Os marked in green have a way out to the border – either directly touching it, or through another Os touching it.

1. Capture Regions on Board: Observations & Logic

1.0. Intuitions

Since we know that all the Os that are connected to the border are safe, we can run a DFS/BFS from each of the Os on the border and mark the visited Os as “safe”. This would be fairly easy if we were allowed to create a new matrix, but since we can’t, how do we somehow add this “safe” information to the matrix?

1.1. Intermediate States

One way to deal with the above problem is that we can covert all the Os that are safe to #s. This will allow us to do two things:

• This let’s us mark Os which are safe.
• While doing DFS/BFS, we will know what all Os have been visited – they are converted to #s now. This will help us avoid infinite loops.

1.2. Cleaning the Board

Well, then what? Once we are done with the DFS or multi-source BFS, we do two things:

• Convert all the remaining Os to Xs, since they were not saved (otherwise they would be #s now)
• Convert all the #s back to Os, saying that they were saved – they had an escape to the border.

2. Capture Regions on Board: Optimized Implementation

2.0. Code

class Solution:
    def solve(self, board):
      # checks whether (i, j) is inside the board or not
        def is_inside(i, j):
            return 0 <= i < m and 0 <= j < n
          
        # convert board's c1 character to c2
        def convert_board(c1, c2):
            for i in range(m):
                for j in range(n):
                    if board[i][j] == c1:
                        board[i][j] = c2
            return 
        
        # runs a dfs from (i, j)
        def dfs(i, j):
          # is (i, j) even in the board? if not, we don't care
            if not is_inside(i, j): return
            
            # is the current cell a non-O? then we don't care
            if board[i][j] != "O": return
            # otherwise we "save" it by converting it to a #
            board[i][j] = "#"
            
            # go over all the neighbours
            for ii, jj in [(i+1, j), (i-1, j), (i, j+1), (i, j-1)]:
                dfs(ii, jj)
            
        m, n = len(board), len(board[0])
        
        # start from all the 4 borders of the board
        for i in range(m): 
            dfs(i, 0)
            dfs(i, n-1)
        for j in range(n): 
            dfs(0, j)
            dfs(m-1, j)
        
        # convert O -> X (captured)
        convert_board('O', 'X')
        # convert # -> O (saved/escaped)
        convert_board('#', 'O')
        
        return
        

2.1. Complexity Analysis

• Time: O(MN), since we might have a case of a board with all Os, so we will convert all of them to #s, taking O(MN) time.
• Space: O(1), we don’t use any auxiliary space.

Tanishq Chaudhary

Producing high-quality intuitive explanations of interview problems. Currently covering LeetCode and InterviewBit.