30. Replace O's with X's

✅ GFG solution to the Replace O's with X's problem: replace all 'O' surrounded by 'X' using boundary traversal and DFS/BFS techniques. 🚀

The problem can be found at the following link: 🔗 Question Link

🧩 Problem Description

You are given a grid[][] of size n*m, where every element is either 'O' or 'X'. Your task is to replace all 'O' or a group of 'O' with 'X' that are surrounded by 'X'.

A 'O' (or a set of 'O') is considered to be surrounded by 'X' if there are 'X' at locations just below, just above, just left and just right of it.

📘 Examples

Example 1

Input: 
grid[][] = [['X', 'X', 'X', 'X'], 
          ['X', 'O', 'X', 'X'], 
          ['X', 'O', 'O', 'X'], 
          ['X', 'O', 'X', 'X'], 
          ['X', 'X', 'O', 'O']]
Output: 
[['X', 'X', 'X', 'X'], 
['X', 'X', 'X', 'X'], 
['X', 'X', 'X', 'X'], 
['X', 'X', 'X', 'X'], 
['X', 'X', 'O', 'O']]
Explanation: We only changed those 'O' that are surrounded by 'X'

Example 2

Input: 
grid[][] = [['X', 'O', 'X', 'X'], 
          ['X', 'O', 'X', 'X'], 
          ['X', 'O', 'O', 'X'], 
          ['X', 'O', 'X', 'X'], 
          ['X', 'X', 'O', 'O']]
Output: 
[['X', 'O', 'X', 'X'], 
['X', 'O', 'X', 'X'], 
['X', 'O', 'O', 'X'], 
['X', 'O', 'X', 'X'], 
['X', 'X', 'O', 'O']]
Explanation: There's no 'O' that's surround by 'X'.

Example 3

Input: 
grid[][] = [['X', 'X', 'X'], 
          ['X', 'O', 'X'], 
          ['X', 'X', 'X']]
Output: 
[['X', 'X', 'X'], 
['X', 'X', 'X'], 
['X', 'X', 'X']]
Explanation: There's only one 'O' that's surround by 'X'.

🔒 Constraints

$1 \le \text{grid.size()} \le 100$
$1 \le \text{grid[0].size()} \le 100$

✅ My Approach

The optimal approach uses boundary traversal with DFS/BFS to identify 'O' cells that are NOT surrounded:

Boundary DFS Marking

Mark Safe Regions:
- Replace all 'O' cells with temporary marker '-' throughout the grid.
- Any 'O' connected to boundary cannot be surrounded.
Traverse Boundaries:
- Start DFS/BFS from all boundary cells containing '-'.
- Mark all connected '-' cells back to 'O' as they are safe from replacement.
Process Four Edges:
- Check top row, bottom row, left column, and right column.
- For each '-' found on boundary, recursively mark all connected regions.
Final Replacement:
- All remaining '-' cells are surrounded, so replace them with 'X'.
- Cells marked as 'O' in step 2 remain unchanged.
Key Insight:
- Instead of finding surrounded regions directly, find regions that touch boundaries.
- Everything else is automatically surrounded.

📝 Time and Auxiliary Space Complexity

Expected Time Complexity: O(m×n), where m is the number of rows and n is the number of columns. Each cell is visited at most twice - once during marking and once during DFS traversal.
Expected Auxiliary Space Complexity: O(m×n), as in the worst case the recursion stack can go as deep as the number of cells in the grid for DFS traversal.

🧑‍💻 Code (C++)

class Solution {
public:
    void fill(vector<vector<char>>& g) {
        int m = g.size(), n = g[0].size();
        for (int i = 0; i < m; i++) for (int j = 0; j < n; j++) if (g[i][j] == 'O') g[i][j] = '-';
        function<void(int, int)> dfs = [&](int i, int j) {
            if (i < 0 || i >= m || j < 0 || j >= n || g[i][j] != '-') return;
            g[i][j] = 'O';
            dfs(i + 1, j); dfs(i - 1, j); dfs(i, j + 1); dfs(i, j - 1);
        };
        for (int i = 0; i < m; i++) { dfs(i, 0); dfs(i, n - 1); }
        for (int j = 0; j < n; j++) { dfs(0, j); dfs(m - 1, j); }
        for (int i = 0; i < m; i++) for (int j = 0; j < n; j++) if (g[i][j] == '-') g[i][j] = 'X';
    }
};

⚡ View Alternative Approaches with Code and Analysis

📊 2️⃣ BFS Queue-Based Approach

💡 Algorithm Steps:

Replace all 'O' with temporary marker '-' throughout the grid.
Use BFS from boundary cells to mark connected regions with 'O'.
Process cells level by level using a queue for breadth-first traversal.
Convert remaining '-' cells to 'X' as they are surrounded regions.

class Solution {
public:
    void fill(vector<vector<char>>& g) {
        int m = g.size(), n = g[0].size();
        queue<pair<int,int>> q;
        for (int i = 0; i < m; i++) for (int j = 0; j < n; j++) {
            if (g[i][j] == 'O') { g[i][j] = '-'; if (i == 0 || i == m - 1 || j == 0 || j == n - 1) q.push({i, j}); }
        }
        int dx[] = {1, -1, 0, 0}, dy[] = {0, 0, 1, -1};
        while (!q.empty()) {
            auto [x, y] = q.front(); q.pop();
            if (g[x][y] != '-') continue;
            g[x][y] = 'O';
            for (int k = 0; k < 4; k++) {
                int nx = x + dx[k], ny = y + dy[k];
                if (nx >= 0 && nx < m && ny >= 0 && ny < n && g[nx][ny] == '-') q.push({nx, ny});
            }
        }
        for (int i = 0; i < m; i++) for (int j = 0; j < n; j++) if (g[i][j] == '-') g[i][j] = 'X';
    }
};

📝 Complexity Analysis:

Time: ⏱️ O(m×n) - Visit each cell at most once
Auxiliary Space: 💾 O(m×n) - Queue can hold all boundary-connected cells

✅ Why This Approach?

Iterative approach avoids stack overflow on large grids
Level-by-level processing provides clear visualization
Better for grids with deep connected components

📊 3️⃣ Union-Find Disjoint Set

💡 Algorithm Steps:

Create virtual dummy node for all boundary-connected regions.
Union all 'O' cells with their adjacent 'O' neighbors.
Union boundary 'O' cells with the dummy node.
Cells not connected to dummy node are surrounded regions.

class Solution {
    vector<int> p;
    int find(int x) { return p[x] == x ? x : p[x] = find(p[x]); }
    void unite(int a, int b) { p[find(a)] = find(b); }
public:
    void fill(vector<vector<char>>& g) {
        int m = g.size(), n = g[0].size();
        p.resize(m * n + 1);
        iota(p.begin(), p.end(), 0);
        int dummy = m * n;
        for (int i = 0; i < m; i++) for (int j = 0; j < n; j++) {
            if (g[i][j] == 'O') {
                int idx = i * n + j;
                if (i == 0 || i == m - 1 || j == 0 || j == n - 1) unite(idx, dummy);
                if (i > 0 && g[i - 1][j] == 'O') unite(idx, (i - 1) * n + j);
                if (j > 0 && g[i][j - 1] == 'O') unite(idx, i * n + j - 1);
            }
        }
        for (int i = 0; i < m; i++) for (int j = 0; j < n; j++)
            if (g[i][j] == 'O' && find(i * n + j) != find(dummy)) g[i][j] = 'X';
    }
};

📝 Complexity Analysis:

Time: ⏱️ O(m×n×α(m×n)) - α is inverse Ackermann function (nearly constant)
Auxiliary Space: 💾 O(m×n) - Parent array for union-find structure

✅ Why This Approach?

Elegant mathematical approach using disjoint sets
Natural way to group connected components
Useful when multiple queries needed on connectivity

📊 4️⃣ Iterative DFS with Stack

💡 Algorithm Steps:

Mark all 'O' cells as temporary marker '-'.
Use explicit stack for DFS to avoid recursion overhead.
Process boundary cells and mark connected components.
Convert remaining '-' to 'X' for surrounded regions.

class Solution {
public:
    void fill(vector<vector<char>>& g) {
        int m = g.size(), n = g[0].size();
        for (int i = 0; i < m; i++) for (int j = 0; j < n; j++) if (g[i][j] == 'O') g[i][j] = '-';
        stack<pair<int,int>> st;
        for (int i = 0; i < m; i++) { if (g[i][0] == '-') st.push({i, 0}); if (g[i][n - 1] == '-') st.push({i, n - 1}); }
        for (int j = 0; j < n; j++) { if (g[0][j] == '-') st.push({0, j}); if (g[m - 1][j] == '-') st.push({m - 1, j}); }
        int dx[] = {1, -1, 0, 0}, dy[] = {0, 0, 1, -1};
        while (!st.empty()) {
            auto [x, y] = st.top(); st.pop();
            if (x < 0 || x >= m || y < 0 || y >= n || g[x][y] != '-') continue;
            g[x][y] = 'O';
            for (int k = 0; k < 4; k++) st.push({x + dx[k], y + dy[k]});
        }
        for (int i = 0; i < m; i++) for (int j = 0; j < n; j++) if (g[i][j] == '-') g[i][j] = 'X';
    }
};

📝 Complexity Analysis:

Time: ⏱️ O(m×n) - Each cell visited once
Auxiliary Space: 💾 O(m×n) - Stack can hold all cells in worst case

✅ Why This Approach?

Avoids recursion stack overflow issues
More control over stack memory usage
DFS benefits with iterative implementation safety

🆚 🔍 Comparison of Approaches

🚀 Approach

⏱️ Time Complexity

💾 Space Complexity

✅ Pros

⚠️ Cons

🔄 Recursive DFS

🟢 O(m×n)

🟡 O(m×n)

🎯 Clean and concise code

⚠️ Stack overflow risk on large grids

🌊 BFS Queue

🟢 O(m×n)

🟡 O(m×n)

🔒 No stack overflow

💾 Extra queue memory

🔗 Union-Find

🟢 O(m×n×α)

🟡 O(m×n)

🧮 Mathematical elegance

🔧 Complex implementation

📚 Iterative DFS

🟢 O(m×n)

🟡 O(m×n)

⚡ DFS benefits without recursion

🔨 More verbose code

🏆 Best Choice Recommendation

🎯 Scenario

🎖️ Recommended Approach

🔥 Performance Rating

🏅 Small to medium grids

🥇 Recursive DFS

★★★★★

🔒 Large grids or safety critical

🥈 BFS Queue

★★★★★

🧮 Multiple connectivity queries

🥉 Union-Find

★★★★☆

⚡ Balance between DFS and safety

🏅 Iterative DFS

★★★★☆

☕ Code (Java)

class Solution {
    public void fill(char[][] g) {
        int m = g.length, n = g[0].length;
        for (int i = 0; i < m; i++) for (int j = 0; j < n; j++) if (g[i][j] == 'O') g[i][j] = '-';
        for (int i = 0; i < m; i++) { dfs(g, i, 0, m, n); dfs(g, i, n - 1, m, n); }
        for (int j = 0; j < n; j++) { dfs(g, 0, j, m, n); dfs(g, m - 1, j, m, n); }
        for (int i = 0; i < m; i++) for (int j = 0; j < n; j++) if (g[i][j] == '-') g[i][j] = 'X';
    }
    void dfs(char[][] g, int i, int j, int m, int n) {
        if (i < 0 || i >= m || j < 0 || j >= n || g[i][j] != '-') return;
        g[i][j] = 'O';
        dfs(g, i + 1, j, m, n); dfs(g, i - 1, j, m, n); dfs(g, i, j + 1, m, n); dfs(g, i, j - 1, m, n);
    }
}

🐍 Code (Python)

class Solution:
    def fill(self, g):
        m, n = len(g), len(g[0])
        for i in range(m):
            for j in range(n):
                if g[i][j] == 'O': g[i][j] = '-'
        def dfs(i, j):
            if i < 0 or i >= m or j < 0 or j >= n or g[i][j] != '-': return
            g[i][j] = 'O'
            dfs(i + 1, j); dfs(i - 1, j); dfs(i, j + 1); dfs(i, j - 1)
        for i in range(m): dfs(i, 0); dfs(i, n - 1)
        for j in range(n): dfs(0, j); dfs(m - 1, j)
        for i in range(m):
            for j in range(n):
                if g[i][j] == '-': g[i][j] = 'X'

🧠 Contribution and Support

For discussions, questions, or doubts related to this solution, feel free to connect on LinkedIn: 📬 Any Questions?. Let's make this learning journey more collaborative!

⭐ If you find this helpful, please give this repository a star! ⭐

📍Visitor Count

Previous29. Graph Diameter Next31. Shortest Cycle

Last updated 2 months ago

hashtag🧩 Problem Description

hashtag📘 Examples

hashtagExample 1

hashtagExample 2

hashtagExample 3

hashtag🔒 Constraints

hashtag✅ My Approach

hashtagBoundary DFS Marking

hashtag📝 Time and Auxiliary Space Complexity

hashtag🧑‍💻 Code (C++)

hashtag📊 2️⃣ BFS Queue-Based Approach

hashtag💡 Algorithm Steps:

hashtag📝 Complexity Analysis:

hashtag✅ Why This Approach?

hashtag📊 3️⃣ Union-Find Disjoint Set

hashtag💡 Algorithm Steps:

hashtag📝 Complexity Analysis:

hashtag✅ Why This Approach?

hashtag📊 4️⃣ Iterative DFS with Stack

hashtag💡 Algorithm Steps:

hashtag📝 Complexity Analysis:

hashtag✅ Why This Approach?

hashtag🆚 🔍 Comparison of Approaches

hashtag🏆 Best Choice Recommendation

hashtag☕ Code (Java)

hashtag🐍 Code (Python)

hashtag🧠 Contribution and Support

hashtag📍Visitor Count

🧩 Problem Description

📘 Examples

Example 1

Example 2

Example 3

🔒 Constraints

✅ My Approach

Boundary DFS Marking

📝 Time and Auxiliary Space Complexity

🧑‍💻 Code (C++)

📊 2️⃣ BFS Queue-Based Approach

💡 Algorithm Steps:

📝 Complexity Analysis:

✅ Why This Approach?

📊 3️⃣ Union-Find Disjoint Set

💡 Algorithm Steps:

📝 Complexity Analysis:

✅ Why This Approach?

📊 4️⃣ Iterative DFS with Stack

💡 Algorithm Steps:

📝 Complexity Analysis:

✅ Why This Approach?

🆚 🔍 Comparison of Approaches

🏆 Best Choice Recommendation

☕ Code (Java)

🐍 Code (Python)

🧠 Contribution and Support

📍Visitor Count