Surrounded Regions

Given an m x n board with X and O, capture all regions of O surrounded by X. A region is not captured if it is connected to the border.

Example 1

Input: [["X","X","X"],["X","O","X"],["X","X","X"]] → Output: [["X","X","X"],["X","X","X"],["X","X","X"]]

Example 2

Input: [["X"]] → Output: [["X"]]

Solution Approach

Union-Find with a virtual "border" node. All O-cells on the border and connected to the border are safe. Mark remaining O-cells as X.

Create virtual node n=m*n (represents border).
For each O on border: union with virtual node.
For each interior O: union with adjacent O cells.
After all unions: any O not connected to virtual node → X.

Java

class Solution {
    int[] parent;
    public void solve(char[][] board) {
        int m = board.length, n = board[0].length;
        parent = new int[m*n+1];
        for (int i = 0; i < parent.length; i++) parent[i]=i;
        int border = m*n;
        for (int i = 0; i < m; i++) for (int j = 0; j < n; j++) {
            if (board[i][j]=='O') {
                int idx=i*n+j;
                if (i==0||i==m-1||j==0||j==n-1) union(idx,border);
                if (i>0 && board[i-1][j]=='O') union(idx,(i-1)*n+j);
                if (j>0 && board[i][j-1]=='O') union(idx,i*n+j-1);
            }
        }
        int borderRoot=find(border);
        for (int i = 0; i < m; i++) for (int j = 0; j < n; j++)
            if (board[i][j]=='O' && find(i*n+j)!=borderRoot) board[i][j]='X';
    }
    private int find(int x) { return parent[x]==x?x:(parent[x]=find(parent[x])); }
    private void union(int a, int b) { parent[find(a)]=find(b); }
}

Time Complexity: O(M*N * alpha(M*N))
Space Complexity: O(M*N)