C++ Union Find with path compression & union by rank
15ms runtime\n1) Scan through grid\n2) Union to previous neighbors(r-1 or c-1) if they are 1\n3) Keep track of all zeros.\n4) Loop through set of zeros & find t
15ms runtime\n1) Scan through grid\n2) Union to previous neighbors(r-1 or c-1) if they are 1\n3) Keep track of all zeros.\n4) Loop through set of zeros & find the area possible if that zero is converted to one.\n5) PROFIT\n```\nclass UF\n{\n    vector<int> p;\n    vector<int> rank; // size of island\n        \n    public:\n    UF(int n)\n    {\n        p=vector<int>(n*n,0);\n        rank=vector<int>(n*n,0);\n    }\n    \n    void makeSet(int i)\n    {\n        p[i]=i;\n        rank[i]=1;\n    }\n    \n    int findSet(int i)\n    {\n        while(i!=p[i])\n        {\n            p[i]=p[p[i]];\n            i=p[i];\n        }\n        \n        return i;\n    }\n    \n    void Union(int a, int b)\n    {\n        int roota=findSet(a);\n        int rootb=findSet(b);\n        \n        if(roota==rootb) return;\n        \n        if(rank[roota]>=rank[rootb])\n        {\n            p[rootb]=roota;\n            rank[roota]+=rank[rootb];\n        }\n        else if(rank[roota]<rank[rootb])\n        {\n            p[roota]=rootb;\n            rank[rootb]+=rank[roota];\n        }\n    }\n    \n    int getSize(int i)\n    {\n        int rooti=findSet(i);\n        \n        return rank[rooti];\n    }\n};\n```\n\n```\nclass Solution {\n    \n    int getPos(int r, int c, int C)\n    {\n        return (r*C)+c;\n    }\n    \n    void getRC(int pos, int N, int& r, int& c)\n    {\n        r=pos/N;\n        c=pos%N;\n    }\npublic:\n    int largestIsland(vector<vector<int>>& grid) {\n        \n        int n=grid.size();\n        \n        UF uf(n); // n*n\n        \n        vector<int> zeros;\n        \n        for(int i=0;i<n;i++)\n        {\n            for(int j=0;j<n;j++)\n            {\n                int curr_pos=getPos(i,j,n);\n                \n                if(grid[i][j]==1)\n                {\n                    uf.makeSet(curr_pos);\n                    if(i>0 && grid[i-1][j]==1)\n                    {\n                        int prev_pos=getPos(i-1,j,n);\n                        uf.Union(curr_pos,prev_pos);\n                    }\n                    \n                    if(j>0 && grid[i][j-1]==1)\n                    {\n                        int prev_pos=getPos(i,j-1,n);\n                        uf.Union(curr_pos,prev_pos);\n                    }\n                }\n                else\n                {\n                    zeros.push_back(curr_pos);\n                }\n            }\n        }\n        \n        int res=0;\n        for(int i=0;i<zeros.size();i++)\n        {\n            unordered_set<int> nei;\n            \n            int r,c;\n            getRC(zeros[i],n,r,c);\n            \n            if(r>0 && grid[r-1][c]==1)\n            {\n                int rootb=uf.findSet(getPos(r-1,c,n));\n                nei.insert(rootb);\n            }\n            \n            if(r<n-1 && grid[r+1][c]==1)\n            {\n                int rootb=uf.findSet(getPos(r+1,c,n));\n                nei.insert(rootb);\n            }\n            \n            if(c>0 && grid[r][c-1]==1)\n            {\n                int rootb=uf.findSet(getPos(r,c-1,n));\n                nei.insert(rootb);\n            }\n            \n            if(c<n-1 && grid[r][c+1]==1)\n            {\n                int rootb=uf.findSet(getPos(r,c+1,n));\n                nei.insert(rootb);\n            }\n            \n            int curr_area=0;\n            for(auto& root: nei)\n            {\n                curr_area+=uf.getSize(root);\n            }\n            \n            res=max(res,curr_area+1);\n        }\n        \n        return (res==0)?n*n:res;\n    }\n};\n```
[]