algoadvance

Leetcode 130. Surrounded Regions

Problem Statement:

You are given an m x n matrix board containing 'X' and 'O'. Capture all regions that are surrounded by 'X'.

A region is captured by flipping all 'O's into 'X's in that surrounded region.

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

Constraints:

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

Clarifying Questions:

1. Should the board be modified in-place? Yes, the board should be modified in place.

2. Is there guaranteed to be at least one ‘O’ in the board? No, there may be boards with only ‘X’s.

Strategy:

1. Identify the Problem: We need to find regions of ‘O’s that are completely surrounded by ‘X’s and flip them to ‘X’.

2. Boundary Check: ‘O’s that are connected to the border cannot be captured. So, we need to identify these ‘O’s first.

3. Traversal Method: Use either DFS or BFS to mark ‘O’s connected to the border as non-capturable.

4. Modify the Board:

   • Traverse the boundary of the board, and for each ‘O’ on the boundary, use DFS or BFS to mark all connected ‘O’s as temporary characters (e.g., ‘T’).
   • Once the boundary traversal is complete, traverse the entire board and flip:
     • ‘O’ to ‘X’ (captured region).
     • ‘T’ back to ‘O’ (regions connected to the border).

Code:

#include <vector>

using namespace std;

class Solution {
public:
    void solve(vector<vector<char>>& board) {
        int m = board.size();
        if (m == 0) return;
        int n = board[0].size();
        
        // Helper lambda to mark connected 'O's from the border
        auto markBorderConnected = [&](int i, int j) {
            if (i < 0 || i >= m || j < 0 || j >= n || board[i][j] != 'O') return;
            board[i][j] = 'T'; // Mark as temporary
            markBorderConnected(i - 1, j); // up
            markBorderConnected(i + 1, j); // down
            markBorderConnected(i, j - 1); // left
            markBorderConnected(i, j + 1); // right
        };

        // Traverse the border to mark all 'O's connected to the boundary
        for (int i = 0; i < m; ++i) {
            markBorderConnected(i, 0); // First column
            markBorderConnected(i, n - 1); // Last column
        }
        for (int j = 1; j < n - 1; ++j) { // Avoid corners since they are already checked
            markBorderConnected(0, j); // First row
            markBorderConnected(m - 1, j); // Last row
        }
        
        // Flip all remaining 'O' to 'X' and 'T' back to 'O'
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (board[i][j] == 'O') {
                    board[i][j] = 'X';
                } else if (board[i][j] == 'T') {
                    board[i][j] = 'O';
                }
            }
        }
    }
};

Time Complexity:

• Traversal of the Border: O(m + n) since we traverse the entire border, consisting of the first and last rows and columns.
• DFS/BFS Traversal: In the worst case, every cell of the board will be visited once. Thus, O(m * n).
• Total Time Complexity: O(m * n).

This solution ensures that all regions of ‘O’s surrounded by ‘X’s are accurately flipped while keeping the border-connected ‘O’s unchanged.

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?