G-14. Surrounded Regions | Replace O's with X's

Transform a given 2D matrix of characters ('X' and 'O') by replacing all 'O' regions completely surrounded by 'X' with 'X'.

1. Why Do We Need This? (Problem Statement & Status Quo)

We are given an $N \times M$ matrix where every cell contains either 'X' or 'O'.

Goal: Replace all 'O's (or groups of connected 'O's) with 'X's if and only if they are completely surrounded by 'X's in all four cardinal directions (top, bottom, left, and right—diagonals are not considered).
The Core Challenge: If a group of 'O's touches the outer boundary of the matrix, can it ever be completely surrounded by 'X's?
- No! Because the boundary itself is open on at least one side (the edge). Therefore, any 'O' that connects directly or indirectly to a boundary 'O' can never be enclosed or converted.

2. Core Mental Model & Real-Life Analogy

Real-Life Analogy: The Island Leak

Imagine a grid of land ('X') containing lakes ('O'). If a lake has a subterranean stream that leads straight out to the ocean (the matrix boundary), pumping water into or trying to wall off that lake is impossible because the water will escape through the boundary connection. Conversely, any inland lake completely sealed off from the boundaries by surrounding land can be filled in (converted to 'X').

Structure & Concept Flow

Matrix Boundaries

[ X X X X X ]

[ X O O X X ] <-- Notice this 'O' group is trapped inside

[ X X O X X ]

[ X X X X X ]

3. Naive vs. Better Approach

Strategy	Approach	Time Complexity	Limitation / Verdict
Naive Approach	Check every internal `'O'` cell individually by scanning outward in 4 directions until hitting a boundary.	$O((N \times M)^2)$	Extremely slow; fails on large matrices due to redundant path scanning and overlapping groups.
Boundary-In Traversal (DFS/BFS)	Start strictly from the boundaries. Flood-fill (`DFS`/`BFS`) inward to mark all `'O'`s connected to the edge as safe. Then, sweep the matrix: convert unmarked `'O'`s to `'X'`, and revert safe `'O'`s back.	$O(N \times M)$	Optimal. Linear time performance, cleanly handles connected components.

4. Step-by-Step Algorithm Evolution

Identify Boundary 'O's: Look along the 4 outer edges of the matrix:
- First row ( $row = 0$ ) and Last row ( $row = N - 1$ ).
- First column ( $col = 0$ ) and Last column ( $col = M - 1$ ).
Flood-Fill Traversal (DFS/BFS): Whenever an 'O' is found on a boundary, trigger a traversal to visit all connected 'O's (horizontally and vertically) and mark them in a separate visited matrix.
Matrix Sweep & Replacement:
- Iterate through every cell in the matrix.
- If a cell is 'O' and unvisited, it means it is trapped inside and has no path to the boundary. Convert it to 'X'.
- If a cell is 'O' and visited, it connects to the boundary. Leave it as 'O'.

5. Complete Flow Walkthrough

Consider a matrix traversal where a boundary 'O' links to internal neighbors:

Structure & Concept Flow

Boundary Cell (4, 0) is 'O'

Calls DFS(4, 0) -> Marks (4, 0) as Visited

Checks Right neighbor (4, 1) -> Found 'O' -> Calls DFS(4, 1)

Checks Top neighbor (3, 1) -> Found 'O' -> Calls DFS(3, 1)

Traversal completes; all connected boundary-linked cells are flagged as visited.

6. Implementation Code (C++ and Java)

C++ Implementation

C++

class Solution {
private:
    void dfs(int row, int col, vector<vector<int>>& vis, 
             vector<vector<char>>& mat, int delRow[], int delCol[], int n, int m) {
        vis[row][col] = 1;
        
        // Check all 4 directions: top, right, bottom, left
        for(int i = 0; i < 4; i++) {
            int nRow = row + delRow[i];
            int nCol = col + delCol[i];
            
            // Check validity, unvisited status, and character 'O'
            if(nRow >= 0 && nRow < n && nCol >= 0 && nCol < m && 
               !vis[nRow][nCol] && mat[nRow][nCol] == 'O') {
                dfs(nRow, nCol, vis, mat, delRow, delCol, n, m);
            }
        }
    }

public:
    void solve(vector<vector<char>>& mat) {
        int n = mat.size();
        int m = mat[0].size();
        
        vector<vector<int>> vis(n, vector<int>(m, 0));
        int delRow[] = {-1, 0, 1, 0};
        int delCol[] = {0, 1, 0, -1};
        
        // Traverse first and last rows
        for(int j = 0; j < m; j++) {
            // First row
            if(!vis[0][j] && mat[0][j] == 'O') {
                dfs(0, j, vis, mat, delRow, delCol, n, m);
            }
            // Last row
            if(!vis[n - 1][j] && mat[n - 1][j] == 'O') {
                dfs(n - 1, j, vis, mat, delRow, delCol, n, m);
            }
        }
        
        // Traverse first and last columns
        for(int i = 0; i < n; i++) {
            // First column
            if(!vis[i][0] && mat[i][0] == 'O') {
                dfs(i, 0, vis, mat, delRow, delCol, n, m);
            }
            // Last column
            if(!vis[i][m - 1] && mat[i][m - 1] == 'O') {
                dfs(i, m - 1, vis, mat, delRow, delCol, n, m);
            }
        }
        
        // Replace unvisited 'O's with 'X's
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < m; j++) {
                if(!vis[i][j] && mat[i][j] == 'O') {
                    mat[i][j] = 'X';
                }
            }
        }
    }
};

Java Implementation

JAVA

class Solution {
    private void dfs(int row, int col, int[][] vis, char[][] mat, int[] delRow, int[] delCol, int n, int m) {
        vis[row][col] = 1;
        
        // Check all 4 directions
        for(int i = 0; i < 4; i++) {
            int nRow = row + delRow[i];
            int nCol = col + delCol[i];
            
            if(nRow >= 0 && nRow < n && nCol >= 0 && nCol < m && 
               vis[nRow][nCol] == 0 && mat[nRow][nCol] == 'O') {
                dfs(nRow, nCol, vis, mat, delRow, delCol, n, m);
            }
        }
    }

    public void solve(char[][] mat) {
        int n = mat.length;
        int m = mat[0].length;
        
        int[][] vis = new int[n][m];
        int[] delRow = {-1, 0, 1, 0};
        int[] delCol = {0, 1, 0, -1};
        
        // Traverse first and last rows
        for(int j = 0; j < m; j++) {
            if(vis[0][j] == 0 && mat[0][j] == 'O') {
                dfs(0, j, vis, mat, delRow, delCol, n, m);
            }
            if(vis[n - 1][j] == 0 && mat[n - 1][j] == 'O') {
                dfs(n - 1, j, vis, mat, delRow, delCol, n, m);
            }
        }
        
        // Traverse first and last columns
        for(int i = 0; i < n; i++) {
            if(vis[i][0] == 0 && mat[i][0] == 'O') {
                dfs(i, 0, vis, mat, delRow, delCol, n, m);
            }
            if(vis[i][m - 1] == 0 && mat[i][m - 1] == 'O') {
                dfs(i, m - 1, vis, mat, delRow, delCol, n, m);
            }
        }
        
        // Replace unvisited 'O's with 'X's
    for(int i = 0; i < n; i++) {
            for(int j = 0; j < m; j++) {
                if(vis[i][j] == 0 && mat[i][j] == 'O') {
                    mat[i][j] = 'X';
                }
            }
        }
    }
}

7. Complexity Analysis

Time Complexity: $O(N \times M)$
- Traversing boundary rows takes $O(M)$ and boundary columns takes $O(N)$ .
- In the worst-case scenario where all cells are 'O', every cell is visited exactly once by the DFS traversal ( $O(N \times M)$ operations).
- The final matrix sweep requires checking every cell once ( $O(N \times M)$ ).
- Overall Time Complexity simplifies to $O(N \times M)$ .
Space Complexity: $O(N \times M)$
- A 2D visited matrix of size $N \times M$ is maintained.
- Recursive DFS call stack depth in the worst case (e.g., a snake-like path traversing all cells) can grow up to $O(N \times M)$ .
- Overall Auxiliary Space Complexity is $O(N \times M)$ .

Summary and Key Takeaways

Boundary Constraint: Any 'O' connected directly or indirectly to the matrix boundary can never be surrounded by 'X'.
Inversion Strategy: Instead of searching outward from inner cells, invert the problem by starting your search inward from boundary 'O's.
Traversal Technique: Use standard graph traversal algorithms (DFS or BFS) with directional delta arrays (delRow, delCol) to inspect all 4 cardinal neighbors.
Matrix Marking: Maintain a separate visited matrix to cleanly track which 'O' components are boundary-connected without corrupting intermediate states.
Final Pass: Sweep the matrix once more; convert any unvisited 'O' to 'X', leaving boundary-linked 'O's untouched.
Optimal Efficiency: The algorithm achieves linear efficiency in both time and space: $O(N \times M)$ .