Replace 'O' with 'X' in a Matrix

The task is to process a matrix, denoted as mat with dimensions N x M, where each element is either 'O' or 'X'. The objective is to replace all instances of 'O' or clusters of 'O' that are enclosed by 'X'. An 'O' (or a group of 'O') is deemed enclosed by 'X' if there are 'X' elements in the positions immediately below, above, left, and right of it.

Input: n = 5, m = 4 

Output

Approach

The boundary elements in the matrix cannot be replaced with ‘X’ as they are not surrounded by ‘X’ from all 4 directions. This means if ‘O’ (or a set of ‘O’) is connected to a boundary ‘O’ then it can’t be replaced with ‘X’. The simple flow is that we start from boundary elements having ‘O’ and go through its neighboring Os in 4 directions and mark them as visited to avoid replacing them with ‘X’.

To mark the O’s group visited DFS method can be used.DFS is a traversal technique that involves the idea of recursion. DFS goes in-depth, i.e., traverses all nodes by going ahead, and when there are no further nodes to traverse in the current path, then it backtracks on the same path and traverses other unvisited nodes.

1. Create a corresponding visited matrix with the same dimensions as that of the input matrix and initialize it to 0.
2. Start with boundary elements, once ‘O’ is found, call the DFS function for that element and mark it as visited. In order to traverse for boundary elements, you can traverse through the first row, last row, first column, and last column.
3. DFS function call will run through all the unvisited neighboring ‘O’s in all 4 directions and mark them as visited so that they are not converted to ‘X’ in the future. The DFS function will not be called for the already visited elements to save time, as they have already been traversed.
4. When all the boundaries are traversed and corresponding sets of ‘O’s are marked as visited, they cannot be replaced with ‘X’. All the other remaining unvisited ‘O’s are replaced with ‘X’.

Complexity

• Time Complexity:  O(N) + O(M) + O(NxMx4) ~ O(N x M)

• Space Complexity: O(N x M)

Where, N = no. of rows in the matrix and M = no. of columns in the matrix.

Code

# Java Code

import java.util.*;

class MatrixReplacer {
    static void depthFirstSearch(int row, int col, int[][] visited, char[][] matrix, int[] delRow, int[] delCol) {
        visited[row][col] = 1;
        int numRows = matrix.length;
        int numCols = matrix[0].length;

        for (int i = 0; i < 4; i++) {
            int newRow = row + delRow[i];
            int newCol = col + delCol[i];

            if (newRow >= 0 && newRow < numRows && newCol >= 0 && newCol < numCols
                    && visited[newRow][newCol] == 0 && matrix[newRow][newCol] == 'O') {
                depthFirstSearch(newRow, newCol, visited, matrix, delRow, delCol);
            }
        }
    }

    static char[][] replaceOs(int numRows, int numCols, char[][] matrix) {
        int[] delRow = {-1, 0, 1, 0};
        int[] delCol = {0, 1, 0, -1};
        int[][] visited = new int[numRows][numCols];

        for (int j = 0; j < numCols; j++) {
            if (visited[0][j] == 0 && matrix[0][j] == 'O') {
                depthFirstSearch(0, j, visited, matrix, delRow, delCol);
            }
            if (visited[numRows - 1][j] == 0 && matrix[numRows - 1][j] == 'O') {
                depthFirstSearch(numRows - 1, j, visited, matrix, delRow, delCol);
            }
        }

        for (int i = 0; i < numRows; i++) {
            if (visited[i][0] == 0 && matrix[i][0] == 'O') {
                depthFirstSearch(i, 0, visited, matrix, delRow, delCol);
            }
            if (visited[i][numCols - 1] == 0 && matrix[i][numCols - 1] == 'O') {
                depthFirstSearch(i, numCols - 1, visited, matrix, delRow, delCol);
            }
        }

        for (int i = 0; i < numRows; i++) {
            for (int j = 0; j < numCols; j++) {
                if (visited[i][j] == 0 && matrix[i][j] == 'O') {
                    matrix[i][j] = 'X';
                }
            }
        }

        return matrix;
    }

    public static void main(String[] args) {
        char[][] matrix = {
                {'X', 'X', 'X', 'X'},
                {'X', 'O', 'X', 'X'},
                {'X', 'O', 'O', 'X'},
                {'X', 'O', 'X', 'X'},
                {'X', 'X', 'O', 'O'}
        };

        int numRows = 5;
        int numCols = 4;

        MatrixReplacer matrixReplacer = new MatrixReplacer();
        char[][] result = matrixReplacer.replaceOs(numRows, numCols, matrix);

        for (int i = 0; i < numRows; i++) {
            for (int j = 0; j < numCols; j++) {
                System.out.print(result[i][j] + " ");
            }
            System.out.println();
        }
    }
}

Output

X X X X 
X X X X 
X X X X 
X O X X 
X X O O