Surrounded Regions Leetcode Problem 130 [Python Solution]

The Surrounded Regions Leetcode problem 130 is a fascinating problem that challenges your skills in handling matrices and regions.

In this problem, you are given an m x n matrix board, which contains only ‘X’ and ‘O’ characters.

Your task is to capture all regions that are surrounded in all four directions by ‘X’.

A region is captured by flipping all ‘O’s within it into ‘X’s.

To illustrate the problem, let’s look at an example:

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

In this example, we capture the regions of ‘O’ surrounded by ‘X’, converting them to ‘X’, but we leave the ‘O’ on the border intact.

It should not be flipped since it is adjacent to an ‘O’ on the border.

Constraints

m == board.length
n == board[i].length
1 <= m, n <= 200
board[i][j] is either ‘X’ or ‘O’.

Understanding Constraints

Before diving into the solution, it’s crucial to understand the constraints:

The input matrix can have a maximum size of 200×200, so the algorithm should be efficient to handle large inputs.
The matrix is filled with ‘X’ and ‘O’, where ‘X’ represents regions that are already surrounded.
Your task is to identify regions of ‘O’s that are surrounded by ‘X’ and convert them to ‘X’ while leaving the ‘O’s on the border or adjacent to ‘X’ as they are.

Now that we’ve grasped the problem, let’s delve into the solution.

Surrounded Regions LeetCode Problem Solution

1. Capture Unsurrounded Regions with Depth-First Search (DFS)

The first phase of our solution involves capturing regions that are not surrounded by ‘X’.

We can achieve this by employing Depth-First Search (DFS) to traverse the matrix.

Our goal is to mark these regions with a temporary value (e.g., ‘T’).

Let’s outline the steps for this phase:

View on GitHub ➹

def solve(self, board: List[List[str]]) -> None:
        """
        Do not return anything, modify board in-place instead.
        """
        # Get the dimensions of the board
        ROWS, COLS = len(board), len(board[0])

        def capture(r, c):
            # Base cases to stop DFS
            if r &lt; 0 or c &lt; 0 or r == ROWS or c == COLS or board[r][c] != "O":
                return

            # Mark the current 'O' as 'T' to indicate it's captured
            board[r][c] = "T"

            # Recursively capture the neighboring 'O's
            capture(r + 1, c)
            capture(r - 1, c)
            capture(r, c + 1)
            capture(r, c - 1)

        # 1. (DFS) Capture unsurrounded regions (O -> T)
        for r in range(ROWS):
            for c in range(COLS):
                if board[r][c] == "O" and (r in [0, ROWS - 1] or c in [0, COLS - 1]):
                    capture(r, c)

        # 2. Capture surrounded regions (O -> X)
        for r in range(ROWS):
            for c in range(COLS):
                if board[r][c] == "O":
                    board[r][c] = "X"

        # 3. Uncapture unsurrounded regions (T -> O)
        for r in range(ROWS):
            for c in range(COLS):
                if board[r][c] == "T":
                    board[r][c] = "O"

In this phase, we traverse the entire board and capture regions by marking ‘O’s as ‘T’ if they are connected to the border of the board.

This phase ensures that only the surrounded regions are left untouched.

2. Capture Surrounded Regions (O -> X)

The second phase is straightforward.

We iterate through the entire matrix and convert any remaining ‘O’s to ‘X’.

Since we’ve already marked the surrounded regions with ‘T’, only the ‘O’s that need to be flipped to ‘X’ will be processed.

    # 2. Capture surrounded regions (O -> X)
    for r in range(ROWS):
        for c in range(COLS):
            if board[r][c] == "O":
                board[r][c] = "X"

Now, all regions that are surrounded by ‘X’ have been captured.

3. Uncapture Unsurrounded Regions (T -> O)

The final phase involves uncapturing the regions that were initially marked with ‘T’.

We revert them to ‘O’, as they were initially part of surrounded regions.

    # 3. Uncapture unsurrounded regions (T -> O)
    for r in range(ROWS):
        for c in range(COLS):
            if board[r][c] == "T":
                board[r][c] = "O"

Time and Space Complexity

The time complexity of this solution is O(m * n) since we iterate through the entire matrix at least once and possibly three times.

The space complexity is O(1), as we modify the input matrix in-place without using additional data structures.

Reasoning Behind Our Approach

The approach presented here leverages a combination of Depth-First Search and a systematic three-phase process to efficiently capture surrounded regions in the matrix.

The main idea is to reverse the problem by first capturing the regions that are not surrounded by ‘X’ (i.e., connected to the border).

This way, we ensure that we mark only the regions that need to be converted to ‘X’.

Subsequently, we convert the remaining ‘O’s to ‘X’ and revert the initially marked ‘T’s back to ‘O’.

The key to understanding this solution lies in the clever reverse thinking strategy, which simplifies the problem and leads to an elegant and efficient algorithm.

In conclusion, solving the Surrounded Regions problem is both intriguing and educational.

By combining Depth-First Search with systematic phase-based processing, we can efficiently identify and capture surrounded regions in the matrix, making this problem an exciting journey in algorithmic thinking.

For more details and to try the problem yourself, visit the LeetCode problem description.

We hope you found this blog post helpful!

If you have any questions or suggestions, please feel free to comment, ask questions, make suggestions, and share this content with others.

Happy coding!