Medium

Surrounded Regions

LAB

Given a board encoded as strings of X and O, flip enclosed O regions to X and return the resulting board.

EXAMPLES

Example 1

Input
{
  "board": [
    "XXXX",
    "XOOX",
    "XXOX",
    "XOXX"
  ]
}

Output
[
  "XXXX",
  "XXXX",
  "XXXX",
  "XOXX"
]

FUNCTION SHAPE

board: stringArray→stringArray

SOLUTION NOTE

Key Insight: Only 'O's not connected to the border should be flipped. So we mark the border-connected ones first, and flip the rest. Just DFS from border O's, and mark them. All remaining O's can be surrounded to become 'X'. Now, we just need to flip the marked border connected O's back to O.

Reveal reference solution +

pythonREFERENCE

def solve(self, board: List[List[str]]) -> None:
    if not board or not board[0]:
        return

    m, n = len(board), len(board[0])

    def dfs(r, c):
        if r < 0 or r >= m or c < 0 or c >= n or board[r][c] != 'O':
            return
        board[r][c] = 'E'  # Mark as escaped
        dfs(r+1, c)
        dfs(r-1, c)
        dfs(r, c+1)
        dfs(r, c-1)

    # Mark border-connected 'O's
    for i in range(m):
        if board[i][0] == 'O':
            dfs(i, 0)
        if board[i][n-1] == 'O':
            dfs(i, n-1)
    for j in range(n):
        if board[0][j] == 'O':
            dfs(0, j)
        if board[m-1][j] == 'O':
            dfs(m-1, j)

    # Flip surrounded 'O' -> 'X', and escaped 'E' -> 'O'
    for i in range(m):
        for j in range(n):
            if board[i][j] == 'O':
                board[i][j] = 'X'
            elif board[i][j] == 'E':
                board[i][j] = 'O'

TimeO(m*n)

SpaceO(m*n)

Open on LeetCode ↗