UnionFind with Size member vs DFS vs BFS||39ms Beats 99.53%
IntuitionTry UnionFind to solve. Since the question asks the size of the largest island by flipping at most 1 extra 0-cell; the Size -optimization is used inste
# Intuition
<!-- Describe your first thoughts on how to solve this problem. -->
Try UnionFind to solve. Since the question asks the size of the largest island by flipping at most 1 extra 0-cell; the Size -optimization is used instead of rank.

Python code is made.
2nd approach uses DFS; 3rd approach uses BFS.
# Approach
<!-- Describe your approach to solving the problem. -->
[Please turn on English subtitle if necessary]
[https://youtu.be/fGyvh325SQc?si=6uLtmIaET_iOueUq](https://youtu.be/fGyvh325SQc?si=6uLtmIaET_iOueUq)
1. Define the Union find class, make all member public, especially `Size`
2. let `n` be a member variable for the class Solution
3. define function  bool `inside(int i, int j)` to check if `(i, j)` is within the `grid`
4. define the function `idx(int i,  int j)` as the mapping value `i*n+j`
5. In `largestIsland(vector<vector<int>>& grid)`, let `n=|grid|, N=n*n`
6. let `int d[5]={0,1,0,-1,0}`  denote the 4 directions  for adjacent cell.
7. Declare the UnionFind object `G(N)`
8. `Let maxSz=1`. Proceed a double loop for each `grid[i][j]==1`, it only consider 2 adjacent cells downward & rightward such as for example
```
if (D>0){// downward where D=(i<n-1)?grid[i+1][j]:0,
    b=a+n;// b=idx(i+1, j)
    if (G.Union(a, b))// connect 2 components where a=idx(i,j)
     maxSz=max(maxSz, G.Size[G.Find(a)]);// Size is public
}
```
9. Use a double loop to transverse `grid[i][j]==0`; it has at most 4 adjacent islands to merge a larger island. Let `int component[4]={N, N, N, N};`
```
for( int a=0; a<4; a++){// 4 directional
    const int r=i+d[a], s=j+d[a+1]; 
    if (inside(r, s) && grid[r][s]!=0) // realy an island
    // set component[cz]= root of this island 
    component[cz++]=G.Find(idx(r, s)); 
}
```
10. If `cz>0`, sort `component`; `sz=1+sum(G.Size[c]  for unique c in component)`; update `maxSz=max(maxSz, sz)`
11. `maxSz` is the answer


# UnionFind makes some quesitions easier
the Union Find class with members `root`, `Size`, `Find`, `Union`, `connected`! The very crucial fact is that **every vertex in a connected component shares a common root, i.e. x is connected to y** $\iff$ Find(x)==Find(y) $\iff$ root[x]==root[y]

Some problems is good solved by used UnionFind

[1971. Find if Path Exists in Graph](https://leetcode.com/problems/find-if-path-exists-in-graph/solutions/5052126/union-find-is-good-vs-dfs-vs-bfs-193ms-beats-99-93)
[2658. Maximum Number of Fish in a Grid](https://leetcode.com/problems/maximum-number-of-fish-in-a-grid/solutions/6337415/ez-dfsc-beats-100-by-anwendeng-nd07/)
[684. Redundant Connection](https://leetcode.com/problems/redundant-connection/solutions/6341974/unionfind-is-goodbeats-100-by-anwendeng-nhlh/)
[959. Regions Cut By Slashes](https://leetcode.com/problems/regions-cut-by-slashes/solutions/5614770/unionfind-dfs-euler-theorem-v-e-f-2-beats-100/)

[Please turn English subtitles if necessary]
[https://youtu.be/cR_D4uA3g3s?si=pRUu-8zRIMmCJHM2](https://youtu.be/cR_D4uA3g3s?si=pRUu-8zRIMmCJHM2)
# UnionFind with Size used in this solution
```cpp [ vector]
// union find class with size
class UnionFind {
public:
    vector<int> root, Size; // Size is public easy for using
    UnionFind(int N): root(N), Size(N, 1){
        iota(root.begin(), root.end(), 0);    
    }
    
    int Find(int x) {
        return (x==root[x]) ? x : root[x] = Find(root[x]);
    }

    bool Union(int x, int y) {       
        x=Find(x), y=Find(y);
        if (x == y) return 0; //already have same root
        if (Size[x] > Size[y]) {
            Size[x] +=Size[y];
            root[y] = x;
        } 
        else {
            Size[y] += Size[x];
            root[x] = y;
        }       
        return 1;// merge 2 disjoint sets
    } 
};
```
```cpp [C array]
class UnionFind {
public:
    int root[250000], Size[250000];
    UnionFind(int N){
        iota(root, root+N, 0);
        fill(Size, Size+N, 1);    
    }
    
    int Find(int x) {
        return (x==root[x]) ? x : root[x] = Find(root[x]);
    }

    bool Union(int x, int y) {       
        x=Find(x), y=Find(y);
        if (x == y) return 0; //already have same root
        if (Size[x] > Size[y]) {
            Size[x] +=Size[y];
            root[y] = x;
        } 
        else {
            Size[y] += Size[x];
            root[x] = y;
        }       
        return 1;// merge 2 disjoint sets
    } 
};
```
# Complexity
- Time complexity:
<!-- Add your time complexity here, e.g. $$O(n)$$ -->
$O(n^2\alpha (n^2))$ where $\alpha(\cdot)$ is the inverse Ackermann function which grows very slowly
- Space complexity:
<!-- Add your space complexity here, e.g. $$O(n)$$ -->
$O(n^2)$
# Code||C++ using Unionfind class with Size| 59 ms Beats 99.33%
```cpp []
class Solution {
public:
    int n;
    inline bool inside(int i, int j){
        return 0<=i && i<n && 0<=j && j<n;
    }
    inline int idx(int i,  int j){
        return i*n+j;
    }
    int largestIsland(vector<vector<int>>& grid) {
        n=grid.size();
        const int N=n*n;
        const int d[5]={0,1,0,-1,0};
        UnionFind G(N);
        int maxSz=1;
        for(int i=0; i<n; i++){
            for(int j=0; j<n; j++){
                if (grid[i][j]){
                    int a=idx(i, j), b;
                    int D=(i<n-1)?grid[i+1][j]:0, R=(j<n-1)?grid[i][j+1]:0;
                    if (D>0){// down
                        b=a+n;
                        if (G.Union(a, b))// connect 2 components
                            maxSz=max(maxSz, G.Size[G.Find(a)]);
                    }
                    if (R>0){// right
                        b=a+1;
                        if (G.Union(a, b))// connect 2 components
                            maxSz=max(maxSz, G.Size[G.Find(a)]);
                    }
                }
            }
        }
        for(int i=0; i<n; i++){
            for(int j=0; j<n; j++){
                if (grid[i][j]==0){
                    int component[4]={N, N, N, N};
                    int cz=0;
                    for( int a=0; a<4; a++){
                        const int r=i+d[a], s=j+d[a+1];
                        if (inside(r, s) && grid[r][s]!=0)
                            component[cz++]=G.Find(idx(r, s));
                    }
                    if (cz==0) continue;
                    sort(component, component+cz);
                    int sz=1+G.Size[component[0]];
                    for (int k=1; k<cz; k++)
                        if (component[k]!=component[k-1]) 
                            sz+=G.Size[component[k]];
                    maxSz=max(maxSz, sz);
                }
            }
        }
        return maxSz;
    }
};




auto init = []() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    return 'c';
}();
```
# Python code slow but accepted
```
class UnionFind:
    def __init__(self, N):
        self.root = list(range(N))
        self.Size = [1]*N

    def Find(self, x):
        if self.root[x] != x:
            self.root[x] = self.Find(self.root[x])  # path compression
        return self.root[x]

    def Union(self, x, y):
        x = self.Find(x)
        y = self.Find(y)
        if x==y: return False

        if self.Size[x] > self.Size[y]:
            self.Size[x] += self.Size[y]
            self.root[y]=x
        else:
            self.Size[y] += self.Size[x]
            self.root[x]=y
        return True

class Solution:
    def largestIsland(self, grid: List[List[int]]) -> int:
        n=len(grid)
        N=n*n
        d=(0, 1, 0, -1, 0)
    
        def inside(i, j):
            return 0<=i<n and 0<=j<n
        def idx(i, j):
            return i*n+j

        G=UnionFind(N)
        maxSz=1
        for i, row in enumerate(grid):
            for j, x in enumerate(row):
                if x==1:
                    a=idx(i, j)
                    D=grid[i+1][j] if i<n-1 else 0
                    R=grid[i][j+1] if j<n-1 else 0
                    if D>0:
                        b=a+n
                        if G.Union(a, b):
                            maxSz=max(maxSz, G.Size[G.Find(a)])
                    if R>0:
                        b=a+1
                        if G.Union(a, b):
                            maxSz=max(maxSz, G.Size[G.Find(a)])
        for i, row in enumerate(grid):
            for j, x in enumerate(row):
                if x==0:
                    component=set()
                    for a in range(4):
                        r, s=i+d[a], j+d[a+1]
                        if inside(r, s) and grid[r][s]==1:
                            component.add(G.Find(idx(r, s)))
                    if len(component)==0: continue
                    sz=1+sum(G.Size[c] for c in component)
                    maxSz=max(maxSz, sz)
        return maxSz

```
# 2nd approach by DFS

1. The 2nd approach replaces DFS in the place of UnionFind to compute the component sizes; the 2nd  loop keeps the same way. the implementation is also very fast. 
2. Each component has a number `comp` which does the similar function of `root` in `UnionFind`; the vector `Size` is for all `component[comp]`
3.  Time complexity is reduced to $O(N)$ where $N=n\times n$
# Code DFS | C++ 39ms Beats 99.53%
```
class Solution {
public:
    int n, N;
    inline bool inside(int i, int j){
        return 0<=i && i<n && 0<=j && j<n;
    }
    inline int idx(int i,  int j){
        return i*n+j;
    }
    const int d[5]={0, 1, 0, -1, 0};
    vector<int> viz;// -1 for unvisited, other for component number

    int dfs(int i, int j, int comp, vector<vector<int>>& grid) {
        viz[idx(i, j)] = comp;
        int cnt = 1;
        for (int a=0; a < 4; a++) {
            int r=i+d[a], s=j+d[a+1];
            if (inside(r, s) && grid[r][s]==1 && viz[idx(r, s)]==-1)
                cnt+= dfs(r, s, comp, grid);
        }
        return cnt;
    }

    int largestIsland(vector<vector<int>>& grid) {
        n = grid.size();
        N = n*n;
        viz.assign(N, -1);
        
        int maxSz=1, comp=0;
        vector<int> Size; // size for component[comp]  

        // Find components
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j]==1 && viz[idx(i, j)]==-1) {
                    int cnt=dfs(i, j, comp++, grid);
                    Size.push_back(cnt);
                    maxSz=max(maxSz, cnt);
                }
            }
        }

        // 2nd loop
        for(int i=0; i<n; i++){
            for(int j=0; j<n; j++){
                if (grid[i][j]==0){
                    int component[4]={N, N, N, N};
                    int cz=0;
                    for( int a=0; a<4; a++){
                        const int r=i+d[a], s=j+d[a+1];
                        if (inside(r, s) && grid[r][s]!=0)
                            component[cz++]=viz[idx(r, s)];
                    }
                    if (cz==0) continue;
                    sort(component, component+cz);
                    int sz=1+Size[component[0]];
                    for (int k=1; k<cz; k++)
                        if (component[k]!=component[k-1]) 
                            sz+=Size[component[k]];
                    maxSz=max(maxSz, sz);
                }
            }
        }
        return maxSz;
    }
};
auto init = []() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    return 'c';
}();
```
# 3rd Approach uses BFS|Just replace dfs in 2nd approach by bfs as follows|87ms Beats 98.81%
```
    int bfs(int i, int j, int comp, vector<vector<int>>& grid){
        queue<int> q;
        int I=idx(i, j);
        q.push(I);
        viz[I]=comp;
        int cnt=0;
        while(!q.empty()){
            int J=q.front(); q.pop();
            auto [i0, j0]=div(J, n);
            cnt++;
            for(int a=0; a<4; a++){
                int r=i0+d[a], s=j0+d[a+1], rs=idx(r, s);
                if (inside(r, s) && grid[r][s]==1 && viz[rs]==-1){
                    q.push(rs);
                    viz[rs]=comp;
                }
            }
        }
        return cnt;
    }
```
['Depth-First Search', 'Breadth-First Search', 'Union Find', 'C++', 'Python3']