NUHMAN.com

Introduction

LeetCode 130: Surrounded Regions is a classic problem that involves modifying a matrix of characters where the task is to find all "O" cells that are completely surrounded by "X" cells, and replace them with "X". The challenge lies in identifying "O" cells that are not surrounded, i.e., cells that are connected to the border of the matrix.

Problem Statement

Given a board containing 'X' and 'O' (the letter O and X), capture all regions surrounded by 'X'. A region is captured by flipping all 'O's into 'X's in that surrounded region.

• A region is captured if and only if it is completely surrounded by 'X'.
• The board is modified in-place.

Example:

go

Input:
board = [
  ['X', 'X', 'X', 'X'],
  ['X', 'O', 'O', 'X'],
  ['X', 'X', 'O', 'X'],
  ['X', 'O', 'X', 'X']
]

Output:
board = [
  ['X', 'X', 'X', 'X'],
  ['X', 'X', 'X', 'X'],
  ['X', 'X', 'X', 'X'],
  ['X', 'O', 'X', 'X']
]

Explanation:

• In this example, the 'O's connected to the border are not captured and remain 'O'.
• The rest of the 'O's, which are completely surrounded by 'X', are changed to 'X'.

Approach:

Depth-First Search (DFS) Approach

The key to solving this problem efficiently is recognizing that any 'O' on the border or connected to the border cannot be captured (i.e., it is not surrounded by 'X'). Hence, we can use a Depth-First Search (DFS) to mark all 'O's connected to the borders as safe (not surrounded).

Here’s the approach step-by-step:

1. DFS from Border 'O' Cells:

• Start a DFS from all 'O's that are connected to the borders (first and last rows, first and last columns).
• These 'O's are marked as "safe" (we can mark them with a special character like 'S').

1. Change Surrounded 'O' to 'X':

• After marking all the border-connected 'O's as safe, iterate through the board. Any remaining 'O' that is not marked as safe is surrounded, so we change it to 'X'.

1. Restore 'S' to 'O':

• Finally, restore the marked 'S' cells back to 'O'.

Edge Case:

• If the matrix is empty or contains only one row/column, the solution should handle these cases appropriately.

Go Implementation

Solution Using DFS

go

package main

import "fmt"

// Directions for moving in four possible directions (up, down, left, right)
var directions = [][2]int{{-1, 0}, {1, 0}, {0, -1}, {0, 1}}

// solve modifies the board by capturing all the regions surrounded by 'X'.
func solve(board [][]byte) {
    if len(board) == 0 || len(board[0]) == 0 {
        return
    }

    // DFS from all border 'O's to mark them as safe
    for i := 0; i < len(board); i++ {
        // Check the first and last columns
        if board[i][0] == 'O' {
            dfs(board, i, 0)
        }
        if board[i][len(board[0])-1] == 'O' {
            dfs(board, i, len(board[0])-1)
        }
    }

    for j := 0; j < len(board[0]); j++ {
        // Check the first and last rows
        if board[0][j] == 'O' {
            dfs(board, 0, j)
        }
        if board[len(board)-1][j] == 'O' {
            dfs(board, len(board)-1, j)
        }
    }

    // Iterate over the board to capture all surrounded regions
    for i := 0; i < len(board); i++ {
        for j := 0; j < len(board[0]); j++ {
            if board[i][j] == 'O' {
                board[i][j] = 'X' // Capture the surrounded 'O'
            } else if board[i][j] == 'S' {
                board[i][j] = 'O' // Restore the 'S' to 'O'
            }
        }
    }
}

// dfs marks the safe 'O's connected to the border.
func dfs(board [][]byte, i, j int) {
    if i < 0 || i >= len(board) || j < 0 || j >= len(board[0]) || board[i][j] != 'O' {
        return
    }
    // Mark the 'O' as safe (using 'S' here)
    board[i][j] = 'S'
    // Perform DFS in all four directions
    for _, dir := range directions {
        dfs(board, i+dir[0], j+dir[1])
    }
}

func main() {
    // Example board
    board := [][]byte{
        {'X', 'X', 'X', 'X'},
        {'X', 'O', 'O', 'X'},
        {'X', 'X', 'O', 'X'},
        {'X', 'O', 'X', 'X'},
    }

    solve(board)
    fmt.Println("Updated board:")
    for _, row := range board {
        fmt.Println(row)
    }
}

Explanation:

1. solve Function:

• This function starts by checking if the board is empty or if its dimensions are zero. If not, it performs DFS from the border 'O' cells to mark all connected 'O's as safe using a special marker 'S'.
• After marking the border-connected 'O's, the function loops through the board to capture all surrounded 'O's (by changing them to 'X'), and then restores all 'S' cells back to 'O'.

1. dfs Function:

• The DFS function explores all four directions (up, down, left, right) from a given cell and marks connected 'O's as safe by changing them to 'S'.
• The DFS ensures that only 'O's connected to the border are marked as safe.

1. Example in main:

• The given board is passed to the solve function, and the result is printed after processing.

Time and Space Complexity

MetricComplexityTime ComplexityO(m * n)Space ComplexityO(m * n)

Time Complexity:

• O(m * n) where m is the number of rows and n is the number of columns in the board. We visit every cell at most once.

Space Complexity:

• O(m * n) due to the recursive stack used for the DFS traversal. In the worst case (when the board is filled with 'O'), we might need space proportional to the number of cells in the board.

Edge Cases

1. Edge Case: Empty Board

• Input: []
• Output: []
• Explanation: An empty board has no cells to process, so the result is the same empty board.

1. Edge Case: Single Row or Single Column

• Input: [['O', 'X']] or [['O'], ['X']]
• Output: Same as input because no 'O' is surrounded.

1. Edge Case: All Border 'O's

• Input: [['O', 'O', 'O'], ['O', 'O', 'O'], ['O', 'O', 'O']]
• Output: Same as input because all 'O's are connected to the border and are not surrounded.

Conclusion

LeetCode 130: Surrounded Regions is a problem that can be efficiently solved using Depth-First Search (DFS). The approach leverages marking the 'O's connected to the border as safe and then capturing all the surrounded 'O's. With an optimal time complexity of O(m * n), this solution efficiently handles the problem in both time and space.