https://leetcode.com/problems/surrounded-regions

In this problem we need to understand, what exactly surrouned by 'X' means. It actually means that if we start from 'O' at the border, and we traverse only 'O', only those 'O' are not surrouned by 'X'. So the plan is the following:

  1. Start dfs or bfs from all 'O', which are on the border.
  2. When we traverse them, let us color them as 'T', temporary color.
  3. Now, when we traverse all we wanted, all colors which are not 'T' need to renamed to 'X' and all colors which are 'T' need to be renamed to 'O', and that is all!

Compexity: time complextiy is O(mn), where m and n are sizes of our board. Additional space complexity can also go upto O(mn) to keep stack of recursion.

class Solution:
    def dfs(self, i, j):
      if i<0 or j<0 or i>=self.M or j>=self.N or self.board[i][j] != "O":
          return
      self.board[i][j] = 'T'
      neib_list = [[i+1,j],[i-1,j],[i,j-1],[i,j+1]]
      for x, y in neib_list:
        self.dfs(x, y)
    
    def solve(self, board):
        if not board: return 0
        self.board, self.M, self.N = board, len(board), len(board[0])
        
        for i in range(0, self.M):
            self.dfs(i,0)
            self.dfs(i,self.N-1)
            
        for j in range(0, self.N):
            self.dfs(0,j)
            self.dfs(self.M-1,j)
        
        for i,j in product(range(self.M), range(self.N)):
            board[i][j] = "X" if board[i][j] != "T" else "O"

If you like the solution, you can upvote it on leetcode discussion section: Problem 0130