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.
Input: [["X","X","X"],["X","O","X"],["X","X","X"]] → Output: [["X","X","X"],["X","X","X"],["X","X","X"]]Input: [["X"]] → Output: [["X"]]
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.
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)