LeetCode 130: Surrounded Regions Solution in Python – A Step-by-Step Guide

Imagine you’re handed a 2D grid—like [["X","X","X","X"], ["X","O","O","X"], ["X","X","O","X"], ["X","O","X","X"]]—filled with 'X's and 'O's, and your task is to flip every 'O' that’s completely surrounded by 'X's into an 'X', while leaving any 'O' connected to the border untouched. This is LeetCode 130: Surrounded Regions, a medium-level problem that’s a captivating mix of grid traversal and connectivity. Using Python, we’ll explore two powerful solutions: the Best Solution, a DFS approach from the borders that’s efficient with O(1) extra space, and an Alternative Solution, a BFS approach from the borders. With detailed examples, code breakdowns, and a friendly tone, this guide will help you conquer those regions—whether you’re new to coding or prepping for an interview. Let’s dive into the grid and flip those 'O's!

What Is LeetCode 130: Surrounded Regions?

In LeetCode 130: Surrounded Regions, you’re given a 2D board (matrix) of characters 'X' and 'O'. Your goal is to modify the board in-place by flipping every 'O' that’s surrounded by 'X's (i.e., not connected to the border) into an 'X', while keeping any 'O' that’s connected to the border (directly or indirectly) as an 'O'. For example, with board = [["X","X","X","X"], ["X","O","O","X"], ["X","X","O","X"], ["X","O","X","X"]], the result is [["X","X","X","X"], ["X","X","X","X"], ["X","X","X","X"], ["X","O","X","X"]], preserving only the bottom-left 'O' connected to the border.

Problem Statement

  • Input: A 2D character array board.
  • Output: None (modify board in-place).
  • Rules:
    • Flip 'O' to 'X' if surrounded by 'X's on all sides (not connected to border).
    • Keep 'O' if connected to any border 'O' via adjacent 'O's (up, down, left, right).
    • 'X's remain unchanged.

Constraints

  • m == board.length
  • n == board[i].length
  • 1 <= m, n <= 200
  • board[i][j] is 'X' or 'O'

Examples

  • 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"]]
    • Why: Only bottom-left 'O' is connected to border.
  • Input: board = [["X"]]
    • Output: [["X"]]
    • Why: No 'O' to flip.
  • Input: board = [["O","O"], ["O","O"]]
    • Output: [["O","O"], ["O","O"]]
    • Why: All 'O's are on border or connected to it.

Understanding the Problem: Flipping the Regions

To solve LeetCode 130: Surrounded Regions in Python, we need to identify which 'O's are surrounded by 'X's and flip them, while preserving 'O's connected to the border. A naive approach—checking every 'O' for connectivity—would be slow and complex. Instead, we’ll use traversal from the borders to mark safe 'O's, then flip the rest:

  • Best Solution (DFS from Borders): O(m*n) time, O(1) extra space—marks in-place.
  • Alternative Solution (BFS from Borders): O(m*n) time, O(m*n) space—uses a queue.

Let’s dive into the Best Solution—DFS from borders—and break it down step-by-step.

Best Solution: DFS from Borders with O(1) Extra Space

Why This Is the Best Solution

The DFS from borders approach is the top choice because it’s both time-efficient—O(m*n)—and space-efficient—O(1) extra space beyond the recursion stack—while being intuitive. It starts at border 'O's, marks all connected 'O's as safe (using a temporary marker), then flips unmarked 'O's to 'X'. It’s like sending scouts from the edges to tag all reachable 'O's, then sweeping through to flip the trapped ones—smart and lean!

How It Works

Here’s the strategy:

  • Step 1: Mark Border-Connected 'O's:
    • Use DFS from each border 'O' to mark connected 'O's with a temporary character (e.g., '#').
  • Step 2: Flip the Board:
    • Scan the board:
      • '#' → 'O' (safe, connected to border).
      • 'O' → 'X' (surrounded).
      • 'X' remains 'X'.
  • Step 3: Modify In-Place:
    • No extra grid needed, uses board itself.

Step-by-Step Example

Example: board = [["X","X","X","X"], ["X","O","O","X"], ["X","X","O","X"], ["X","O","X","X"]]

  • Initial Board:

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

  • Step 1: DFS from Borders:
    • Top row: No 'O's.
    • Bottom row: (3,1) 'O' → DFS marks only (3,1).
    • Left column: (3,0) 'O' already marked.
    • Right column: No 'O's.
    • Updated (after marking):

X X X X X O O X X X O X X # X X

  • Step 2: Flip:
    • '#' → 'O', 'O' → 'X', 'X' → 'X'.
    • Final:

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

  • Result: Board modified in-place.

Code with Detailed Line-by-Line Explanation

Here’s the Python code, explained clearly:

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])

        # Step 1: DFS function to mark connected 'O's
        def dfs(i, j):
            if i < 0 or i >= m or j < 0 or j >= n or board[i][j] != 'O':
                return
            board[i][j] = '#'  # Mark as safe
            dfs(i+1, j)  # Down
            dfs(i-1, j)  # Up
            dfs(i, j+1)  # Right
            dfs(i, j-1)  # Left

        # Step 2: Mark border 'O's and connected ones
        # Top and bottom borders
        for j in range(n):
            if board[0][j] == 'O':
                dfs(0, j)
            if board[m-1][j] == 'O':
                dfs(m-1, j)
        # Left and right borders
        for i in range(m):
            if board[i][0] == 'O':
                dfs(i, 0)
            if board[i][n-1] == 'O':
                dfs(i, n-1)

        # Step 3: Flip the board
        for i in range(m):
            for j in range(n):
                if board[i][j] == '#':
                    board[i][j] = 'O'  # Restore safe 'O's
                elif board[i][j] == 'O':
                    board[i][j] = 'X'  # Flip surrounded 'O's
  • Line 4-6: Handle empty board.
  • Line 8: Get dimensions.
  • Line 11-18: DFS to mark connected 'O's:
    • Line 12-13: Check bounds and value.
    • Line 14-18: Mark and recurse in four directions.
  • Line 21-29: Mark border 'O's:
    • Line 22-25: Top and bottom.
    • Line 27-29: Left and right.
  • Line 32-36: Flip board:
    • Line 34: Restore '#'.
    • Line 36: Flip 'O' to 'X'.
  • Time Complexity: O(m*n)—each cell visited once.
  • Space Complexity: O(1)—only recursion stack (O(m*n) worst case).

This is a border-scouting genius!

Alternative Solution: BFS from Borders

Why an Alternative Approach?

The BFS from borders approach offers a queue-based alternative—O(mn) time, O(mn) space—starting from border 'O's and marking connected regions. It’s useful for those who prefer BFS or need explicit control over traversal order. It’s like sending a wave from the edges to tag all reachable 'O's—methodical and clear!

How It Works

  • Step 1: Queue border 'O's.
  • Step 2: BFS to mark connected 'O's.
  • Step 3: Flip unmarked 'O's to 'X'.

Step-by-Step Example

Example: board = [["X","X","X","X"], ["X","O","O","X"], ["X","X","O","X"], ["X","O","X","X"]]

  • Step 1: Queue Borders:
    • Queue: [(3,1)].
  • Step 2: BFS:
    • (3,1): Mark '#'.
    • No adjacent 'O's.
  • Step 3: Flip:
    • Same final result as above.
  • Result: Same board.

Code for BFS Approach

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])
        queue = deque()

        # Step 1: Queue border 'O's
        for j in range(n):
            if board[0][j] == 'O':
                queue.append((0, j))
            if board[m-1][j] == 'O':
                queue.append((m-1, j))
        for i in range(m):
            if board[i][0] == 'O':
                queue.append((i, 0))
            if board[i][n-1] == 'O':
                queue.append((i, n-1))

        # Step 2: BFS to mark connected 'O's
        directions = [(1,0), (-1,0), (0,1), (0,-1)]
        while queue:
            i, j = queue.popleft()
            if board[i][j] != 'O':
                continue
            board[i][j] = '#'
            for di, dj in directions:
                ni, nj = i + di, j + dj
                if 0 <= ni < m and 0 <= nj < n and board[ni][nj] == 'O':
                    queue.append((ni, nj))

        # Step 3: Flip the board
        for i in range(m):
            for j in range(n):
                if board[i][j] == '#':
                    board[i][j] = 'O'
                elif board[i][j] == 'O':
                    board[i][j] = 'X'
  • Line 8-19: Queue border 'O's.
  • Line 22-30: BFS to mark:
    • Line 26-30: Explore four directions.
  • Line 33-37: Flip board.
  • Time Complexity: O(m*n).
  • Space Complexity: O(m*n)—queue size.

It’s a wave-spreading marker!

Comparing the Two Solutions

  • DFS (Best):
    • Pros: O(m*n) time, O(1) extra space, intuitive.
    • Cons: Recursion stack (O(m*n) worst case).
  • BFS (Alternative):
    • Pros: O(m*n) time, explicit queue control.
    • Cons: O(m*n) space for queue.

DFS wins for space efficiency.

Additional Examples and Edge Cases

  • [["O"]]: [["O"]].
  • [["X","O"], ["O","X"]]: [["X","O"], ["O","X"]].
  • [["X"]]: [["X"]].

Both handle these perfectly.

Complexity Breakdown

  • DFS: Time O(m*n), Space O(1) (O(m*n) stack).
  • BFS: Time O(m*n), Space O(m*n).

DFS’s leaner space shines.

Key Takeaways

  • DFS: Scout from borders!
  • BFS: Wave from edges!
  • Connectivity: Border 'O's are key.
  • Python Tip: In-place rocks—see [Python Basics](/python/basics).

Final Thoughts: Flip the Grid

LeetCode 130: Surrounded Regions in Python is a grid-flipping adventure. The DFS approach marks with finesse, while BFS offers a steady wave. Want more grid fun? Try LeetCode 200: Number of Islands or LeetCode 79: Word Search. Ready to flip? Head to Solve LeetCode 130 on LeetCode and conquer those regions today!