Skip to content

130. Surrounded Regions

On LeetCode ->

Problem

Modify board in place: change every O component that does not touch the border into X. Cells connect horizontally or vertically.

Before: XXXX    After: XXXX
        XOOX           XXXX
        XXOX           XXXX
        XOXX           XOXX

Key trick

Invert the problem: mark every border-connected O as safe, capture all remaining Os, then restore the safe cells.

Trap

  • Checking only whether each O is on the border instead of whether its entire component reaches the border.
  • Using recursive DFS in Python, which can exceed the recursion limit on a board containing many connected cells.
  • Restoring temporary markers before all surrounded cells have been captured.

Why is it interesting?

It turns a difficult enclosed-region test into a simple reachability search starting from the border.

Python solution

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

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

        def mark(r, c):
            if board[r][c] != "O":
                return

            # Mark border-connected cells as safe using iterative DFS.
            board[r][c] = "#"
            stack = [(r, c)]

            while stack:
                r, c = stack.pop()

                for dr, dc in ((-1, 0), (1, 0), (0, -1), (0, 1)):
                    nr, nc = r + dr, c + dc
                    if 0 <= nr < m and 0 <= nc < n and board[nr][nc] == "O":
                        board[nr][nc] = "#"
                        stack.append((nr, nc))

        # Regions connected to any border cannot be captured.
        for r in range(m):
            mark(r, 0)
            mark(r, n - 1)

        for c in range(n):
            mark(0, c)
            mark(m - 1, c)

        # Capture surrounded cells and restore safe cells.
        for r in range(m):
            for c in range(n):
                if board[r][c] == "O":
                    board[r][c] = "X"
                elif board[r][c] == "#":
                    board[r][c] = "O"
  • Time complexity: \(O(mn)\)
  • Space complexity: \(O(mn)\) in the worst case for the DFS stack

Comment on my solution

Your algorithm is correct and has optimal \(O(mn)\) time complexity.

  • The border set works, but it is unnecessary; DFS can be started directly from each border cell.
  • Recursive DFS may raise RecursionError for a large connected region, so an explicit stack is safer in Python.
  • The two final traversals can be combined into one.
  • Marking cells in place correctly avoids a separate visited set.
class Solution:
    def solve(self, board: list[list[str]]) -> None:
        # [["X","X","X","X"],      [["X","X","X","X"],
        #  ["X","O","O","X"], ->    ["X","X","X","X"],
        #  ["X","X","O","X"],       ["X","X","X","X"],
        #  ["X","O","X","X"]],      ["X","O","X","X"]]

        # - start dfs on "O" that are on the edges to mark component
        #   that can't be surrended.
        #   - mark them with "#"
        # - convert "O" to "X" on zeros not part of these edge component
        # - revert "#" to "O"

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

        for r in [0, m - 1]:
            for c in range(n):
                if board[r][c] == "O":
                    o_edges.add((r,c))

        for c in [0, n - 1]:
            for r in range(m):
                if board[r][c] == "O":
                    o_edges.add((r,c))

        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] = "#" # mark the cell

            for nei, nej in [r - 1, c], [r + 1, c], [r, c - 1], [r, c + 1]:
                dfs(nei, nej)

        for r, c in o_edges:
            if board[r][c] == "O":
                dfs(r, c)

        for r in range(m):
            for c in range(n):
                if board[r][c] == "O":
                    board[r][c] = "X"

        for r in range(m):
            for c in range(n):
                if board[r][c] == "#":
                    board[r][c] = "O"