Leetcode - 130. Surrounded Regions

🚀 Approach

We use a Breadth-First Search (BFS) approach starting from the border 'O's. Any 'O' connected to a border is safe and should not be flipped. These safe 'O's are temporarily marked as 'T'.

Steps:

1. Traverse the border cells of the board:

• First and last row.
• First and last column.
• Start BFS from every border 'O'.

1. Inside BFS:

• For each 'O' visited, mark it as 'T'.
• Add all connected 'O's to the queue and continue.

1. Post-processing:

• All 'T's are part of safe regions → revert them to 'O'.
• All remaining 'O's are surrounded → flip them to 'X'.

---

✅ Code

/**
 * @param {character[][]} board
 * @return {void} Do not return anything, modify board in-place instead.
 */
var solve = function (board) {
    let visited = new Set();


    function bfs(r, c) {
        board[r][c] = "T";
        let queue = [[r, c]];
        visited.add(JSON.stringify([r, c]));
        while (queue.length > 0) {
            let [row, col] = queue.shift();
            const directions = [[1, 0], [-1, 0], [0, 1], [0, -1]];
            for (let [dr, dc] of directions) {
                let newRow = row + dr;
                let newCol = col + dc;
                if (newRow >= 0 && newRow < board.length &&
                    newCol >= 0 && newCol < board[0].length && board[newRow][newCol] == "O" && !visited.has(JSON.stringify([newRow, newCol]))) {
                    visited.add(JSON.stringify([newRow, newCol]));
                    board[newRow][newCol] = "T";
                    queue.push([newRow, newCol]);
                }
            }
        }
    }
    // traversing the border of board for ex [["X","X","X","X"],["X","O","O","X"],["X","X","O","X"],["X","O","X","X"]]

    const rows = board.length;
    const cols = board[0].length;

    for (let i = 0; i < rows; i++) {
        if (board[i][0] === "O") bfs(i, 0); //first row 
        if (board[i][cols - 1] === "O") bfs(i, cols - 1); //last row
    }
    for (let j = 0; j < cols; j++) {
        if (board[0][j] === "O") bfs(0, j); // first column
        if (board[rows - 1][j] === "O") bfs(rows - 1, j); //last column
    }

    //in the end all T's are replaced with O , rest with X
    for (let i = 0; i < rows; i++) {
        for (let j = 0; j < cols; j++) {
            if (board[i][j] == "T") {
                board[i][j] = "O";
            } else {
                board[i][j] = "X";
            }
        }
    }

};

---

⏱️ Time & Space Complexity

Time Complexity: O(m × n)

• We visit each cell at most once during the BFS traversal and final sweep.

Space Complexity: O(m × n)

• In the worst case, the queue and visited set can hold all cells (when the whole board is 'O's).

---

🧩 Final Thoughts

This BFS approach makes it super clear which 'O's are safe (connected to the border), and which should be flipped. It avoids unnecessary recursion stack growth compared to DFS and gives good control over the traversal.

---