algoadvance

Leetcode 130. Surrounded Regions

Problem Statement

You are given an m x n matrix board containing 'X' and 'O' (the letter O).

Capture all regions that are 4-directionally surrounded by 'X'. A region is captured by flipping all 'O's into 'X's in that surrounded region.

Example 1:

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"]]
Explanation: Surrounded regions should not be on the border, which means that any 'O' on the border of the board are not flipped to 'X'. Any 'O' that is not on the border and it is not connected to an 'O' on the border will be flipped to 'X'. Two cells inside the board which are 'O' and not on the border, will be flipped to 'X'. One cell that is 'O' and on the border remains 'O'.

Example 2:

Input: board = [["X"]]
Output: [["X"]]

Constraints:

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

Clarifying Questions

1. Do we need to handle edge cases where the board has minimum values (i.e., 1x1 matrix)?
   • Yes, we need to ensure the solution handles the smallest case efficiently.
2. Are there any specific constraints on time complexity?
   • No explicit constraints mentioned, but the solution should be optimal given the possible matrix size of 200x200.

Strategy

1. Initial Observations:
   • Any ‘O’ connected to a border ‘O’ cannot be flipped.
   • We can mark all ‘O’s connected to the border initially and mark them as safe.
2. Steps:
   • Traverse the border of the matrix and perform a DFS or BFS for each ‘O’ found, marking the connected ‘O’s as safe.
   • Flip all the remaining ‘O’s to ‘X’ as they are surrounded.
   • Restore the marked ‘safe’ positions back to ‘O’.
3. Detailed Plan:
   • Use DFS/BFS starting from each border ‘O’ to mark safe regions.
   • Use a temporary marker to differentiate between ‘O’s to be flipped and those connected to the border.

Here is the implementation:

Code

public class Solution {
    public void solve(char[][] board) {
        if (board == null || board.length == 0) return;

        int rows = board.length;
        int cols = board[0].length;
        
        // Mark border O's and their connected O's as 'S' (safe)
        for (int i = 0; i < rows; i++) {
            if (board[i][0] == 'O') dfs(board, i, 0);
            if (board[i][cols - 1] == 'O') dfs(board, i, cols - 1);
        }
        for (int j = 0; j < cols; j++) {
            if (board[0][j] == 'O') dfs(board, 0, j);
            if (board[rows - 1][j] == 'O') dfs(board, rows - 1, j);
        }
        
        // Flip all remaining 'O' to 'X' and safe 'S' back to 'O'
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (board[i][j] == 'O') board[i][j] = 'X';
                if (board[i][j] == 'S') board[i][j] = 'O';
            }
        }
    }

    private void dfs(char[][] board, int i, int j) {
        if (i < 0 || i >= board.length || j < 0 || j >= board[0].length || board[i][j] != 'O') {
            return;
        }
        board[i][j] = 'S';
        dfs(board, i - 1, j);
        dfs(board, i + 1, j);
        dfs(board, i, j - 1);
        dfs(board, i, j + 1);
    }
}

Time Complexity

• Time Complexity: O(m * n), where m is the number of rows and n is the number of columns, since we potentially touch each cell multiple times in the worst case.
• Space Complexity: O(m * n) for the recursion stack in the worst case when all cells are ‘O’.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?