Leetcode 130. Surrounded Regions

Problem

Leetcode 130 - Surrounded Regions

Example:

Input: board = [["X","X","X","X"],["X","O","O","X"],["X","X","O","X"],["X","O","X","X"]]
Output: [["X","X","X","X"],["X","X","X","X"],["X","X","X","X"],["X","O","X","X"]]

Input: board = [["X"]]
Output: [["X"]]

Approach

Using DFS, we can convert the ones that’s connected to edge we can convert all the ones that’s connected to edge as ‘T’ for temporary

Once we convert all the ones that are connected to the edges, we can then loop through the board.

• if board[i][j] == ‘T’, then they should be ‘O’
• if board[i][j] == ‘O’, then they should be ‘X’ since they are the ‘surrounded ones’

Here is the Python code for the solution:

class Solution:
    def solve(self, board: List[List[str]]) -> None:
        """
        Do not return anything, modify board in-place instead.
        """
        def check(i, j):
            if i < 0 or i >= len(board) or j < 0 or j >= len(board[0]) or board[i][j] != 'O':
                return 
            board[i][j] = 'T'
            check(i+1, j)
            check(i-1, j)
            check(i, j+1)
            check(i, j-1)

        for i in range(len(board)):
            if board[i][0] == 'O':
                check(i, 0)
            if board[i][len(board[0])-1] == 'O':
                check(i, len(board[0])-1)

        for j in range(len(board[0])):
            if board[0][j] == 'O':
                check(0, j)
            if board[len(board)-1][j] == 'O':
                check(len(board)-1, j)
        
        for i in range(len(board)):
            for j in range(len(board[0])):
                if board[i][j] == 'O':
                    board[i][j] = 'X'
                if board[i][j] == 'T':
                    board[i][j] = 'O'

Time Complexity and Space Complexity

Time Complexity: $O(n*m)$

Space Complexity: $O(n*m)$