Leetcode 130. Surrounded Regions (Python)

Related Topic

Depth-First-Search.

Description

Given a 2D board containing ‘X’ and ‘O’ (the letter O), capture all regions surrounded by ‘X’.

A region is captured by flipping all ‘O’s into ‘X’s in that surrounded region.

Sample I/O

Example 1

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

After running your function, the board should be:

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

Explanation:

Surrounded regions shouldn’t 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.

Methodology

This question can be solved by Depth First Search and It is similar with question 200. Number of Islands. You can treat the regions to be islands inside the border(not on the border)

To find the surrounded regions, we can first find the on boarder regions and mark them. After we find all on border regions. Then we iterate the board again, make the surround regions to be ‘X’ and on border regions to be ‘O’

Code

def solve(self, board: List[List[str]]) -> None:
        """
        Do not return anything, modify board in-place instead.
        """
        if not board: return board
        row,col=len(board),len(board[0])
        directions=[(-1,0),(0,1),(1,0),(0,-1)]
        visited=set()
        def dfs(x,y):
            for dx, dy in directions:
                nx,ny=x+dx,y+dy
                if 0<=nx<row and 0<=ny<col and board[nx][ny]=='O' and (nx,ny) not in visited:
                    visited.add((nx,ny))
                    board[nx][ny]='G'
                    dfs(nx, ny)
                
        for x in range(row):
            for y in range(col):
                if (x==0 or x==row-1 or y== 0 or y==col-1) and board[x][y] == 'O' and (x,y) not in visited:
                    board[x][y]='G'
                    visited.add((x,y))
                    dfs(x,y)
                    
        for x in range(row):
            for y in range(col):
                if board[x][y]=='O':
                    board[x][y]='X'
                elif board[x][y]=='G':
                    board[x][y]='O'

BigO

We iterate each cell will cost O(m*n) where m*n is the size of the 2D list. Each cell will also iterate four directions O(m*n*4) Then we iterate twice to render the on border regions and surrounded regions which take O(2*m*n). In total O(6*m*n)