Surrounded Regions

🎯

Surrounded Regions

mediumGRAPHAmazonFacebookGoogle

Imagine a map of lakes and land where lakes completely enclosed by land need to be drained. How do you identify which lakes are truly enclosed?

💡 This problem involves identifying regions in a grid that are completely surrounded by another type of cell. Beginners often struggle because it requires understanding how to traverse grids and mark connected components, especially those connected to boundaries.

📋

Problem Statement

Given an m x n matrix board containing 'X' and 'O', capture all regions surrounded by 'X'. A region is captured by flipping all 'O's into 'X's in that surrounded region. An 'O' region is considered surrounded if it is not connected to any 'O' on the boundary of the board.

1 ≤ m, n ≤ 200board[i][j] is 'X' or 'O'

💡

Example

Input"[['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']]

The 'O's in the middle are surrounded by 'X' and flipped, but the 'O' connected to the boundary remains.

• All 'O's on the boundary → no flips
• Single cell board with 'O' → no flips
• Board with no 'O's → no changes
• Board with all 'O's → only boundary 'O's remain

⚠️

Common Mistakes

Flipping 'O's connected to boundary by mistake

Incorrect output with boundary 'O's changed to 'X'

✅ Always mark and preserve boundary-connected 'O's before flipping

Not marking visited cells leading to infinite loops

Stack overflow or infinite loop during DFS/BFS

✅ Use a visited array or mark cells during traversal

Only checking immediate neighbors without full region traversal

Partial flipping, missing connected 'O's

✅ Use DFS/BFS to explore entire connected region

Modifying the board while traversing without marking safe cells

Incorrect traversal results and wrong final board

✅ Use temporary marks (like 'S') to differentiate safe cells

🧠

Brute Force (Check Each 'O' Region Separately)

💡 This approach exists to build intuition by directly checking each 'O' region for boundary connection, even though it's inefficient. It helps understand the problem's core challenge.

Intuition

For each 'O', explore its connected region to see if it touches the boundary. If not, flip all 'O's in that region to 'X'.

Algorithm

1. Iterate over each cell in the board.
2. When an 'O' is found, perform DFS/BFS to find all connected 'O's.
3. Check if any 'O' in this region touches the boundary.
4. If no boundary 'O' found, flip all 'O's in this region to 'X'.

💡 The challenge is managing repeated searches and ensuring you don't flip regions connected to the boundary.

</>

Code

from collections import deque

def solve(board):
    if not board or not board[0]:
        return
    m, n = len(board), len(board[0])
    visited = [[False]*n for _ in range(m)]

    def bfs(r, c):
        queue = deque([(r, c)])
        region = [(r, c)]
        visited[r][c] = True
        touches_boundary = r == 0 or r == m-1 or c == 0 or c == n-1
        while queue:
            x, y = queue.popleft()
            for dx, dy in [(-1,0),(1,0),(0,-1),(0,1)]:
                nx, ny = x+dx, y+dy
                if 0 <= nx < m and 0 <= ny < n and not visited[nx][ny] and board[nx][ny] == 'O':
                    visited[nx][ny] = True
                    queue.append((nx, ny))
                    region.append((nx, ny))
                    if nx == 0 or nx == m-1 or ny == 0 or ny == n-1:
                        touches_boundary = True
        return region, touches_boundary

    for i in range(m):
        for j in range(n):
            if board[i][j] == 'O' and not visited[i][j]:
                region, touches_boundary = bfs(i, j)
                if not touches_boundary:
                    for x, y in region:
                        board[x][y] = 'X'

# Example usage:
if __name__ == '__main__':
    board = [
        ['X','X','X','X'],
        ['X','O','O','X'],
        ['X','X','O','X'],
        ['X','O','X','X']
    ]
    solve(board)
    for row in board:
        print(row)

Line Notes

if not board or not board[0]:Check for empty input to avoid errors

visited = [[False]*n for _ in range(m)]Track visited cells to avoid repeated work

def bfs(r, c):Define BFS to explore connected 'O' region

touches_boundary = r == 0 or r == m-1 or c == 0 or c == n-1Initialize boundary touch flag

if nx == 0 or nx == m-1 or ny == 0 or ny == n-1:Update flag if region touches boundary

if board[i][j] == 'O' and not visited[i][j]:Start BFS only on unvisited 'O's

if not touches_boundary:Flip region only if not connected to boundary

import java.util.*;

public class SurroundedRegions {
    public void solve(char[][] board) {
        if (board == null || board.length == 0) return;
        int m = board.length, n = board[0].length;
        boolean[][] visited = new boolean[m][n];

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (board[i][j] == 'O' && !visited[i][j]) {
                    List<int[]> region = new ArrayList<>();
                    boolean touchesBoundary = bfs(board, visited, i, j, region);
                    if (!touchesBoundary) {
                        for (int[] cell : region) {
                            board[cell[0]][cell[1]] = 'X';
                        }
                    }
                }
            }
        }
    }

    private boolean bfs(char[][] board, boolean[][] visited, int r, int c, List<int[]> region) {
        int m = board.length, n = board[0].length;
        Queue<int[]> queue = new LinkedList<>();
        queue.offer(new int[]{r, c});
        visited[r][c] = true;
        region.add(new int[]{r, c});
        boolean touchesBoundary = r == 0 || r == m - 1 || c == 0 || c == n - 1;

        int[][] directions = {{-1,0},{1,0},{0,-1},{0,1}};
        while (!queue.isEmpty()) {
            int[] curr = queue.poll();
            for (int[] d : directions) {
                int nr = curr[0] + d[0], nc = curr[1] + d[1];
                if (nr >= 0 && nr < m && nc >= 0 && nc < n && !visited[nr][nc] && board[nr][nc] == 'O') {
                    visited[nr][nc] = true;
                    queue.offer(new int[]{nr, nc});
                    region.add(new int[]{nr, nc});
                    if (nr == 0 || nr == m - 1 || nc == 0 || nc == n - 1) {
                        touchesBoundary = true;
                    }
                }
            }
        }
        return touchesBoundary;
    }

    // Driver code
    public static void main(String[] args) {
        SurroundedRegions sr = new SurroundedRegions();
        char[][] board = {
            {'X','X','X','X'},
            {'X','O','O','X'},
            {'X','X','O','X'},
            {'X','O','X','X'}
        };
        sr.solve(board);
        for (char[] row : board) {
            System.out.println(Arrays.toString(row));
        }
    }
}

Line Notes

if (board == null || board.length == 0) return;Guard clause for empty input

boolean[][] visited = new boolean[m][n];Track visited cells to prevent reprocessing

boolean touchesBoundary = r == 0 || r == m - 1 || c == 0 || c == n - 1;Initialize boundary touch flag

if (board[i][j] == 'O' && !visited[i][j])Start BFS only on unvisited 'O's

visited[nr][nc] = true;Mark cells visited when added to queue

if (nr == 0 || nr == m - 1 || nc == 0 || nc == n - 1)Update flag if region touches boundary

if (!touchesBoundary)Flip region only if not connected to boundary

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

class Solution {
public:
    void solve(vector<vector<char>>& board) {
        if (board.empty() || board[0].empty()) return;
        int m = board.size(), n = board[0].size();
        vector<vector<bool>> visited(m, vector<bool>(n, false));

        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (board[i][j] == 'O' && !visited[i][j]) {
                    vector<pair<int,int>> region;
                    bool touchesBoundary = bfs(board, visited, i, j, region);
                    if (!touchesBoundary) {
                        for (auto& cell : region) {
                            board[cell.first][cell.second] = 'X';
                        }
                    }
                }
            }
        }
    }

private:
    bool bfs(vector<vector<char>>& board, vector<vector<bool>>& visited, int r, int c, vector<pair<int,int>>& region) {
        int m = board.size(), n = board[0].size();
        queue<pair<int,int>> q;
        q.push({r, c});
        visited[r][c] = true;
        region.push_back({r, c});
        bool touchesBoundary = (r == 0 || r == m - 1 || c == 0 || c == n - 1);

        int dirs[4][2] = {{-1,0},{1,0},{0,-1},{0,1}};
        while (!q.empty()) {
            auto [x, y] = q.front(); q.pop();
            for (auto& d : dirs) {
                int nx = x + d[0], ny = y + d[1];
                if (nx >= 0 && nx < m && ny >= 0 && ny < n && !visited[nx][ny] && board[nx][ny] == 'O') {
                    visited[nx][ny] = true;
                    q.push({nx, ny});
                    region.push_back({nx, ny});
                    if (nx == 0 || nx == m - 1 || ny == 0 || ny == n - 1) {
                        touchesBoundary = true;
                    }
                }
            }
        }
        return touchesBoundary;
    }
};

int main() {
    Solution sol;
    vector<vector<char>> board = {
        {'X','X','X','X'},
        {'X','O','O','X'},
        {'X','X','O','X'},
        {'X','O','X','X'}
    };
    sol.solve(board);
    for (auto& row : board) {
        for (char c : row) cout << c << ' ';
        cout << '\n';
    }
    return 0;
}

Line Notes

if (board.empty() || board[0].empty()) return;Check for empty input to avoid errors

vector<vector<bool>> visited(m, vector<bool>(n, false));Track visited cells to avoid repeated work

bool touchesBoundary = (r == 0 || r == m - 1 || c == 0 || c == n - 1);Initialize boundary touch flag

if (board[i][j] == 'O' && !visited[i][j])Start BFS only on unvisited 'O's

visited[nx][ny] = true;Mark cells visited when added to queue

if (nx == 0 || nx == m - 1 || ny == 0 || ny == n - 1)Update flag if region touches boundary

if (!touchesBoundary)Flip region only if not connected to boundary

function solve(board) {
    if (!board || board.length === 0) return;
    const m = board.length, n = board[0].length;
    const visited = Array.from({length: m}, () => Array(n).fill(false));

    function bfs(r, c) {
        const queue = [[r, c]];
        const region = [[r, c]];
        visited[r][c] = true;
        let touchesBoundary = r === 0 || r === m - 1 || c === 0 || c === n - 1;

        while (queue.length) {
            const [x, y] = queue.shift();
            for (const [dx, dy] of [[-1,0],[1,0],[0,-1],[0,1]]) {
                const nx = x + dx, ny = y + dy;
                if (nx >= 0 && nx < m && ny >= 0 && ny < n && !visited[nx][ny] && board[nx][ny] === 'O') {
                    visited[nx][ny] = true;
                    queue.push([nx, ny]);
                    region.push([nx, ny]);
                    if (nx === 0 || nx === m - 1 || ny === 0 || ny === n - 1) {
                        touchesBoundary = true;
                    }
                }
            }
        }
        return [region, touchesBoundary];
    }

    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            if (board[i][j] === 'O' && !visited[i][j]) {
                const [region, touchesBoundary] = bfs(i, j);
                if (!touchesBoundary) {
                    for (const [x, y] of region) {
                        board[x][y] = 'X';
                    }
                }
            }
        }
    }
}

// Example usage:
const board = [
    ['X','X','X','X'],
    ['X','O','O','X'],
    ['X','X','O','X'],
    ['X','O','X','X']
];
solve(board);
console.log(board);

Line Notes

if (!board || board.length === 0) return;Guard clause for empty input

const visited = Array.from({length: m}, () => Array(n).fill(false));Track visited cells to avoid repeated work

let touchesBoundary = r === 0 || r === m - 1 || c === 0 || c === n - 1;Initialize boundary touch flag

if (board[i][j] === 'O' && !visited[i][j])Start BFS only on unvisited 'O's

visited[nx][ny] = true;Mark cells visited when added to queue

if (nx === 0 || nx === m - 1 || ny === 0 || ny === n - 1)Update flag if region touches boundary

if (!touchesBoundary)Flip region only if not connected to boundary

⏱

Complexity

TimeO(m*n*(m+n))

SpaceO(m*n)

For each 'O', BFS explores connected region which can be large; repeated BFS leads to high complexity.

💡 For a 10x10 board, this could mean up to 100 BFS traversals, each visiting many cells, causing slow performance.

Interview Verdict: TLE / Inefficient for large boards

This approach is too slow for large inputs but helps understand the problem and is a good starting point.

🧠

Better Approach (Mark Boundary-Connected 'O's First)

💡 This approach improves efficiency by only marking 'O's connected to the boundary, avoiding repeated BFS for each region.

Intuition

Instead of checking each region, start from boundary 'O's and mark all connected 'O's as safe. Then flip all unmarked 'O's.

Algorithm

1. Traverse the boundary cells and perform DFS/BFS on 'O's to mark them as safe.
2. Iterate over the entire board, flipping unmarked 'O's to 'X'.
3. Restore marked safe 'O's back to 'O' if temporary marks were used.

💡 This approach cleverly reverses the problem by focusing on what should NOT be flipped.

</>

Code

def solve(board):
    if not board or not board[0]:
        return
    m, n = len(board), len(board[0])

    def dfs(r, c):
        if r < 0 or r >= m or c < 0 or c >= n or board[r][c] != 'O':
            return
        board[r][c] = 'S'  # Mark safe
        for dr, dc in [(-1,0),(1,0),(0,-1),(0,1)]:
            dfs(r+dr, c+dc)

    for i in range(m):
        if board[i][0] == 'O': dfs(i, 0)
        if board[i][n-1] == 'O': dfs(i, n-1)
    for j in range(n):
        if board[0][j] == 'O': dfs(0, j)
        if board[m-1][j] == 'O': dfs(m-1, j)

    for i in range(m):
        for j in range(n):
            if board[i][j] == 'O':
                board[i][j] = 'X'
            elif board[i][j] == 'S':
                board[i][j] = 'O'

# Example usage:
if __name__ == '__main__':
    board = [
        ['X','X','X','X'],
        ['X','O','O','X'],
        ['X','X','O','X'],
        ['X','O','X','X']
    ]
    solve(board)
    for row in board:
        print(row)

Line Notes

if not board or not board[0]:Check for empty input

board[r][c] = 'S'Mark 'O's connected to boundary as safe

for i in range(m):Start DFS from left and right boundaries

for j in range(n):Start DFS from top and bottom boundaries

if board[i][j] == 'O':Flip surrounded 'O's to 'X'

elif board[i][j] == 'S':Restore safe 'O's

public class SurroundedRegions {
    public void solve(char[][] board) {
        if (board == null || board.length == 0) return;
        int m = board.length, n = board[0].length;

        for (int i = 0; i < m; i++) {
            dfs(board, i, 0);
            dfs(board, i, n - 1);
        }
        for (int j = 0; j < n; j++) {
            dfs(board, 0, j);
            dfs(board, m - 1, j);
        }

        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] == 'S') board[i][j] = 'O';
            }
        }
    }

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

    public static void main(String[] args) {
        SurroundedRegions sr = new SurroundedRegions();
        char[][] board = {
            {'X','X','X','X'},
            {'X','O','O','X'},
            {'X','X','O','X'},
            {'X','O','X','X'}
        };
        sr.solve(board);
        for (char[] row : board) {
            System.out.println(java.util.Arrays.toString(row));
        }
    }
}

Line Notes

if (board == null || board.length == 0) return;Guard clause for empty input

board[r][c] = 'S';Mark boundary-connected 'O's as safe

dfs(board, i, 0);Start DFS from left boundary

dfs(board, 0, j);Start DFS from top boundary

if (board[i][j] == 'O') board[i][j] = 'X';Flip surrounded 'O's

else if (board[i][j] == 'S') board[i][j] = 'O';Restore safe 'O's

#include <iostream>
#include <vector>
using namespace std;

class Solution {
public:
    void solve(vector<vector<char>>& board) {
        if (board.empty() || board[0].empty()) return;
        int m = board.size(), n = board[0].size();

        for (int i = 0; i < m; ++i) {
            dfs(board, i, 0);
            dfs(board, i, n - 1);
        }
        for (int j = 0; j < n; ++j) {
            dfs(board, 0, j);
            dfs(board, m - 1, j);
        }

        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] == 'S') board[i][j] = 'O';
            }
        }
    }

private:
    void dfs(vector<vector<char>>& board, int r, int c) {
        int m = board.size(), n = board[0].size();
        if (r < 0 || r >= m || c < 0 || c >= n || board[r][c] != 'O') return;
        board[r][c] = 'S';
        dfs(board, r - 1, c);
        dfs(board, r + 1, c);
        dfs(board, r, c - 1);
        dfs(board, r, c + 1);
    }
};

int main() {
    Solution sol;
    vector<vector<char>> board = {
        {'X','X','X','X'},
        {'X','O','O','X'},
        {'X','X','O','X'},
        {'X','O','X','X'}
    };
    sol.solve(board);
    for (auto& row : board) {
        for (char c : row) cout << c << ' ';
        cout << '\n';
    }
    return 0;
}

Line Notes

if (board.empty() || board[0].empty()) return;Check for empty input

board[r][c] = 'S';Mark boundary-connected 'O's as safe

dfs(board, i, 0);Start DFS from left boundary

dfs(board, 0, j);Start DFS from top boundary

if (board[i][j] == 'O') board[i][j] = 'X';Flip surrounded 'O's

else if (board[i][j] == 'S') board[i][j] = 'O';Restore safe 'O's

function solve(board) {
    if (!board || board.length === 0) return;
    const m = board.length, n = board[0].length;

    function dfs(r, c) {
        if (r < 0 || r >= m || c < 0 || c >= n || board[r][c] !== 'O') return;
        board[r][c] = 'S';
        dfs(r - 1, c);
        dfs(r + 1, c);
        dfs(r, c - 1);
        dfs(r, c + 1);
    }

    for (let i = 0; i < m; i++) {
        dfs(i, 0);
        dfs(i, n - 1);
    }
    for (let j = 0; j < n; j++) {
        dfs(0, j);
        dfs(m - 1, j);
    }

    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            if (board[i][j] === 'O') board[i][j] = 'X';
            else if (board[i][j] === 'S') board[i][j] = 'O';
        }
    }
}

// Example usage:
const board = [
    ['X','X','X','X'],
    ['X','O','O','X'],
    ['X','X','O','X'],
    ['X','O','X','X']
];
solve(board);
console.log(board);

Line Notes

if (!board || board.length === 0) return;Guard clause for empty input

board[r][c] = 'S';Mark boundary-connected 'O's as safe

dfs(i, 0);Start DFS from left boundary

dfs(0, j);Start DFS from top boundary

if (board[i][j] === 'O') board[i][j] = 'X';Flip surrounded 'O's

else if (board[i][j] === 'S') board[i][j] = 'O';Restore safe 'O's

⏱

Complexity

TimeO(m*n)

SpaceO(m*n) due to recursion stack or queue

Each cell is visited at most once during DFS from boundary, making it linear in board size.

💡 For a 10x10 board, this means at most 100 cells visited once, which is efficient.

Interview Verdict: Accepted / Efficient for large boards

This approach is optimal and commonly expected in interviews for this problem.

🧠

Optimal Approach (Use BFS Instead of DFS for Boundary Marking)

💡 This approach uses BFS to mark boundary-connected 'O's, which can be easier to implement iteratively and avoids recursion stack overflow.

Intuition

Start BFS from all boundary 'O's simultaneously, marking connected 'O's safe, then flip the rest.

Algorithm

1. Add all boundary 'O's to a queue.
2. While queue not empty, pop cell and mark connected 'O's as safe.
3. After BFS, flip all unmarked 'O's to 'X' and restore safe marks.

💡 This approach uses a queue to iteratively mark safe regions, avoiding recursion.

</>

Code

from collections import deque

def solve(board):
    if not board or not board[0]:
        return
    m, n = len(board), len(board[0])
    queue = deque()

    for i in range(m):
        for j in [0, n-1]:
            if board[i][j] == 'O':
                queue.append((i, j))
                board[i][j] = 'S'
    for j in range(n):
        for i in [0, m-1]:
            if board[i][j] == 'O':
                queue.append((i, j))
                board[i][j] = 'S'

    while queue:
        x, y = queue.popleft()
        for dx, dy in [(-1,0),(1,0),(0,-1),(0,1)]:
            nx, ny = x + dx, y + dy
            if 0 <= nx < m and 0 <= ny < n and board[nx][ny] == 'O':
                board[nx][ny] = 'S'
                queue.append((nx, ny))

    for i in range(m):
        for j in range(n):
            if board[i][j] == 'O':
                board[i][j] = 'X'
            elif board[i][j] == 'S':
                board[i][j] = 'O'

# Example usage:
if __name__ == '__main__':
    board = [
        ['X','X','X','X'],
        ['X','O','O','X'],
        ['X','X','O','X'],
        ['X','O','X','X']
    ]
    solve(board)
    for row in board:
        print(row)

Line Notes

queue = deque()Initialize queue for BFS

board[i][j] == 'O'Add boundary 'O's to queue and mark safe

while queue:Process all safe connected 'O's iteratively

board[nx][ny] = 'S'Mark connected 'O's safe to avoid revisiting

if board[i][j] == 'O':Flip surrounded 'O's

elif board[i][j] == 'S':Restore safe 'O's

import java.util.*;

public class SurroundedRegions {
    public void solve(char[][] board) {
        if (board == null || board.length == 0) return;
        int m = board.length, n = board[0].length;
        Queue<int[]> queue = new LinkedList<>();

        for (int i = 0; i < m; i++) {
            if (board[i][0] == 'O') {
                queue.offer(new int[]{i, 0});
                board[i][0] = 'S';
            }
            if (board[i][n - 1] == 'O') {
                queue.offer(new int[]{i, n - 1});
                board[i][n - 1] = 'S';
            }
        }
        for (int j = 0; j < n; j++) {
            if (board[0][j] == 'O') {
                queue.offer(new int[]{0, j});
                board[0][j] = 'S';
            }
            if (board[m - 1][j] == 'O') {
                queue.offer(new int[]{m - 1, j});
                board[m - 1][j] = 'S';
            }
        }

        int[][] directions = {{-1,0},{1,0},{0,-1},{0,1}};
        while (!queue.isEmpty()) {
            int[] curr = queue.poll();
            for (int[] d : directions) {
                int nr = curr[0] + d[0], nc = curr[1] + d[1];
                if (nr >= 0 && nr < m && nc >= 0 && nc < n && board[nr][nc] == 'O') {
                    board[nr][nc] = 'S';
                    queue.offer(new int[]{nr, nc});
                }
            }
        }

        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] == 'S') board[i][j] = 'O';
            }
        }
    }

    public static void main(String[] args) {
        SurroundedRegions sr = new SurroundedRegions();
        char[][] board = {
            {'X','X','X','X'},
            {'X','O','O','X'},
            {'X','X','O','X'},
            {'X','O','X','X'}
        };
        sr.solve(board);
        for (char[] row : board) {
            System.out.println(Arrays.toString(row));
        }
    }
}

Line Notes

Queue<int[]> queue = new LinkedList<>();Initialize queue for BFS

board[i][0] == 'O'Add boundary 'O's to queue and mark safe

while (!queue.isEmpty())Iteratively process safe connected 'O's

board[nr][nc] = 'S';Mark connected 'O's safe to avoid revisiting

if (board[i][j] == 'O') board[i][j] = 'X';Flip surrounded 'O's

else if (board[i][j] == 'S') board[i][j] = 'O';Restore safe 'O's

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

class Solution {
public:
    void solve(vector<vector<char>>& board) {
        if (board.empty() || board[0].empty()) return;
        int m = board.size(), n = board[0].size();
        queue<pair<int,int>> q;

        for (int i = 0; i < m; ++i) {
            if (board[i][0] == 'O') {
                q.push({i, 0});
                board[i][0] = 'S';
            }
            if (board[i][n - 1] == 'O') {
                q.push({i, n - 1});
                board[i][n - 1] = 'S';
            }
        }
        for (int j = 0; j < n; ++j) {
            if (board[0][j] == 'O') {
                q.push({0, j});
                board[0][j] = 'S';
            }
            if (board[m - 1][j] == 'O') {
                q.push({m - 1, j});
                board[m - 1][j] = 'S';
            }
        }

        int dirs[4][2] = {{-1,0},{1,0},{0,-1},{0,1}};
        while (!q.empty()) {
            auto [x, y] = q.front(); q.pop();
            for (auto& d : dirs) {
                int nx = x + d[0], ny = y + d[1];
                if (nx >= 0 && nx < m && ny >= 0 && ny < n && board[nx][ny] == 'O') {
                    board[nx][ny] = 'S';
                    q.push({nx, ny});
                }
            }
        }

        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] == 'S') board[i][j] = 'O';
            }
        }
    }
};

int main() {
    Solution sol;
    vector<vector<char>> board = {
        {'X','X','X','X'},
        {'X','O','O','X'},
        {'X','X','O','X'},
        {'X','O','X','X'}
    };
    sol.solve(board);
    for (auto& row : board) {
        for (char c : row) cout << c << ' ';
        cout << '\n';
    }
    return 0;
}

Line Notes

queue<pair<int,int>> q;Initialize queue for BFS

board[i][0] == 'O'Add boundary 'O's to queue and mark safe

while (!q.empty())Iteratively process safe connected 'O's

board[nx][ny] = 'S';Mark connected 'O's safe to avoid revisiting

if (board[i][j] == 'O') board[i][j] = 'X';Flip surrounded 'O's

else if (board[i][j] == 'S') board[i][j] = 'O';Restore safe 'O's

function solve(board) {
    if (!board || board.length === 0) return;
    const m = board.length, n = board[0].length;
    const queue = [];

    for (let i = 0; i < m; i++) {
        if (board[i][0] === 'O') {
            queue.push([i, 0]);
            board[i][0] = 'S';
        }
        if (board[i][n - 1] === 'O') {
            queue.push([i, n - 1]);
            board[i][n - 1] = 'S';
        }
    }
    for (let j = 0; j < n; j++) {
        if (board[0][j] === 'O') {
            queue.push([0, j]);
            board[0][j] = 'S';
        }
        if (board[m - 1][j] === 'O') {
            queue.push([m - 1, j]);
            board[m - 1][j] = 'S';
        }
    }

    while (queue.length) {
        const [x, y] = queue.shift();
        for (const [dx, dy] of [[-1,0],[1,0],[0,-1],[0,1]]) {
            const nx = x + dx, ny = y + dy;
            if (nx >= 0 && nx < m && ny >= 0 && ny < n && board[nx][ny] === 'O') {
                board[nx][ny] = 'S';
                queue.push([nx, ny]);
            }
        }
    }

    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            if (board[i][j] === 'O') board[i][j] = 'X';
            else if (board[i][j] === 'S') board[i][j] = 'O';
        }
    }
}

// Example usage:
const board = [
    ['X','X','X','X'],
    ['X','O','O','X'],
    ['X','X','O','X'],
    ['X','O','X','X']
];
solve(board);
console.log(board);

Line Notes

const queue = [];Initialize queue for BFS

board[i][0] === 'O'Add boundary 'O's to queue and mark safe

while (queue.length)Iteratively process safe connected 'O's

board[nx][ny] = 'S';Mark connected 'O's safe to avoid revisiting

if (board[i][j] === 'O') board[i][j] = 'X';Flip surrounded 'O's

else if (board[i][j] === 'S') board[i][j] = 'O';Restore safe 'O's

⏱

Complexity

TimeO(m*n)

SpaceO(m*n) due to queue

Each cell is visited once during BFS from boundary, making it linear in board size.

💡 This approach is efficient and avoids recursion stack issues, suitable for large boards.

Interview Verdict: Accepted / Optimal and robust

This is the preferred approach in interviews for its clarity and efficiency.

📊

All Approaches - One-Glance Tradeoffs

💡 In interviews, approach 2 or 3 is preferred for clarity and efficiency; brute force is good to mention but not to code fully.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	O(m*n*(m+n))	O(m*n)	Yes (deep recursion or large BFS queues)	N/A	Mention only - never code fully
2. Boundary DFS Marking	O(m*n)	O(m*n) recursion stack	Possible on large boards	N/A	Code this approach in most interviews
3. Boundary BFS Marking	O(m*n)	O(m*n) queue	No	N/A	Good alternative to DFS, especially for large inputs

💼

Interview Strategy

💡 Use this guide to understand the problem deeply, practice all approaches, and prepare to explain tradeoffs clearly in interviews.

How to Present

Clarify the problem and constraints with the interviewer.Describe the brute force approach to show understanding of the problem.Explain the better approach using boundary marking and why it is more efficient.Optionally mention BFS as an alternative to DFS for robustness.Write clean, tested code and discuss complexity and edge cases.

Time Allocation

Clarify: 2min → Approach: 5min → Code: 10min → Test: 3min. Total ~20min

What the Interviewer Tests

The interviewer tests your ability to identify boundary-connected regions, implement graph traversal on grids, and optimize from brute force to efficient solutions.

Common Follow-ups

• What if the board is very large? → Use BFS to avoid recursion stack overflow.
• Can you do it in-place without extra space? → Yes, by marking cells temporarily on the board.

💡 These follow-ups test your understanding of space optimization and robustness in implementation.

🔍

Pattern Recognition

When to Use

1) Grid with 'O' and 'X' cells, 2) Need to identify surrounded regions, 3) Boundary connectivity matters, 4) Flip or mark regions based on connectivity

Signature Phrases

regions surrounded by 'X'connected to boundaryflip all 'O's in surrounded regions

NOT This Pattern When

Problems that only require counting islands without boundary conditions or problems involving shortest paths

Similar Problems

Number of Islands - also uses grid DFS/BFS to find connected componentsWalls and Gates - identifies regions connected to boundariesFlood Fill - marks connected regions in a grid

Practice

1. You are given a list of courses and their prerequisite pairs. You need to determine if it is possible to finish all courses without running into a circular dependency. Which algorithmic approach guarantees an optimal solution to detect such cycles in the course dependency graph?

easy

A. Perform a topological sort using Kahn's Algorithm (BFS) to detect cycles by checking if all nodes can be processed.

B. Use a brute force approach that tries all possible course orders to find a valid sequence.

C. Apply dynamic programming to count the number of ways to complete courses without cycles.

D. Use a greedy algorithm that always picks the course with the fewest prerequisites first.

Solution

1. Step 1: Understand the problem as cycle detection in a directed graph

   The problem requires detecting if a cycle exists in the course prerequisite graph, which invalidates any course order.

2. Step 2: Identify the algorithm that detects cycles efficiently

   Kahn's Algorithm performs a topological sort using BFS and in-degree counts. If all nodes are processed, no cycle exists; otherwise, a cycle is detected.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Topological sort with BFS is the standard cycle detection method for this problem [OK]

Hint: Topological sort detects cycles by processing all nodes [OK]

Common Mistakes:

• Greedy approach fails on complex dependencies
• Dynamic programming is not suited for cycle detection
• Brute force is inefficient and impractical

2. You are given a directed acyclic graph with n nodes and a list of edges. You want to find the smallest set of nodes such that starting a traversal from these nodes can reach every other node in the graph. Which approach guarantees finding this minimal set efficiently?

easy

A. Perform BFS from each node and pick the nodes that can reach all others.

B. Identify all nodes with zero in-degree and return them as the minimal set.

C. Identify all nodes with zero in-degree and return them as the minimal set.

D. Use a dynamic programming approach to count paths from each node.

Solution

1. Step 1: Understand the problem constraints

   The problem requires the minimal set of vertices from which all nodes are reachable. Nodes with zero in-degree are exactly those that no other node reaches, so they must be included.

2. Step 2: Analyze approaches

   Performing BFS from each node is inefficient. Dynamic programming counting paths is unnecessary. The minimal set is precisely all nodes with zero in-degree.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Minimal set corresponds exactly to zero in-degree nodes [OK]

Hint: Minimal set corresponds exactly to zero in-degree nodes [OK]

Common Mistakes:

• Assuming BFS from each node is efficient
• Confusing zero in-degree nodes with minimal set without justification
• Using DP which is unnecessary here

3. You are given a grid representing oranges where each cell can be empty, fresh, or rotten. Every minute, any fresh orange adjacent (up, down, left, right) to a rotten orange becomes rotten. Which algorithmic approach guarantees the minimum time to rot all fresh oranges or determine if impossible?

easy

A. Greedy approach that rots the freshest orange closest to any rotten orange each minute

B. Multi-source Breadth-First Search (BFS) starting from all rotten oranges simultaneously

C. Dynamic Programming to store minimum rot times for each cell independently

D. Depth-First Search (DFS) from a single rotten orange to propagate rot times

Solution

1. Step 1: Understand problem dynamics

   The rot spreads simultaneously from all rotten oranges each minute, so processing them in parallel is essential.

2. Step 2: Identify algorithm that models simultaneous spread

   Multi-source BFS naturally simulates spreading from multiple sources in waves, ensuring minimum time to rot all reachable fresh oranges.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Multi-source BFS models simultaneous spread correctly [OK]

Hint: Rot spreads simultaneously -> multi-source BFS needed [OK]

Common Mistakes:

• Using DFS from one source misses simultaneous spread
• Greedy picks local best but not global minimum
• DP doesn't fit simultaneous wave propagation

4. What is the time complexity of the BFS-based algorithm to find the maximum area of an island in an m x n grid, where each cell is visited at most once?

medium

A. O((m * n)^2) -- BFS could revisit cells multiple times in worst case

B. O(m + n) -- because BFS visits each row and column once

C. O(m * n) -- each cell is visited once and neighbors checked constant times

D. O(m * n) plus extra O(m * n) space for the visited set

Solution

1. Step 1: Identify BFS visits each cell at most once

   Each cell is enqueued and dequeued once, so total operations proportional to number of cells.

2. Step 2: Each cell checks up to 4 neighbors in constant time

   Neighbor checks are constant per cell, so total is O(m*n).

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Linear in grid size, no repeated visits [OK]

Hint: Each cell visited once -> O(m*n) time [OK]

Common Mistakes:

• Assuming BFS revisits cells multiple times
• Confusing rows+cols with total cells
• Ignoring constant neighbor checks

5. Examine the following buggy code snippet for the minimum effort path problem. Which line contains the subtle bug that can cause incorrect results or inefficiency?

medium

A. Line initializing dist with infinity values

B. Line checking if effort > dist[r][c] to skip outdated entries

C. Line calculating next_effort using sum of efforts instead of max

D. Line pushing new effort and coordinates into the heap

Solution

1. Step 1: Identify cost calculation

   The problem requires minimizing the maximum edge effort, but the code sums efforts, which is incorrect.

2. Step 2: Understand impact

   Summing efforts leads to wrong path cost and incorrect minimal effort path.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Replacing sum with max fixes correctness [OK]

Hint: Min effort = max edge, not sum [OK]

Common Mistakes:

• Using sum instead of max for effort
• Skipping heap entries incorrectly
• Misinitializing dist array