Striver method  || GodofGraph 🔥🔥
Intuition\n Describe your first thoughts on how to solve this problem. \n\n# Approach\n Describe your approach to solving the problem. \n\n# Complexity\n- Time 
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass DisjointSet {\n\npublic:\n    vector<int> rank, parent, size;\n    DisjointSet(int n) {\n        rank.resize(n + 1, 0);\n        parent.resize(n + 1);\n        size.resize(n + 1);\n        for (int i = 0; i <= n; i++) {\n            parent[i] = i;\n            size[i] = 1;\n        }\n    }\n\n    int findUPar(int node) {\n        if (node == parent[node])\n            return node;\n        return parent[node] = findUPar(parent[node]);\n    }\n\n    void unionByRank(int u, int v) {\n        int ulp_u = findUPar(u);\n        int ulp_v = findUPar(v);\n        if (ulp_u == ulp_v) return;\n        if (rank[ulp_u] < rank[ulp_v]) {\n            parent[ulp_u] = ulp_v;\n        }\n        else if (rank[ulp_v] < rank[ulp_u]) {\n            parent[ulp_v] = ulp_u;\n        }\n        else {\n            parent[ulp_v] = ulp_u;\n            rank[ulp_u]++;\n        }\n    }\n\n    void unionBySize(int u, int v) {\n        int ulp_u = findUPar(u);\n        int ulp_v = findUPar(v);\n        if (ulp_u == ulp_v) return;\n        if (size[ulp_u] < size[ulp_v]) {\n            parent[ulp_u] = ulp_v;\n            size[ulp_v] += size[ulp_u];\n        }\n        else {\n            parent[ulp_v] = ulp_u;\n            size[ulp_u] += size[ulp_v];\n        }\n    }\n};\nclass Solution {\n    private:\n    bool isValid(int newr, int newc, int n) {\n        return newr >= 0 && newr < n && newc >= 0 && newc < n;\n    }\npublic:\n    int largestIsland(vector<vector<int>>& grid) {\n         int n = grid.size();\n        DisjointSet ds(n * n);\n        // step - 1\n        for (int row = 0; row < n ; row++) {\n            for (int col = 0; col < n ; col++) {\n                if (grid[row][col] == 0) continue;\n                int dr[] = { -1, 0, 1, 0};\n                int dc[] = {0, -1, 0, 1};\n                for (int ind = 0; ind < 4; ind++) {\n                    int newr = row + dr[ind];\n                    int newc = col + dc[ind];\n                    if (isValid(newr, newc, n) && grid[newr][newc] == 1) {\n                        int nodeNo = row * n + col;\n                        int adjNodeNo = newr * n + newc;\n                        ds.unionBySize(nodeNo, adjNodeNo);\n                    }\n                }\n            }\n        }\n        // step 2\n        int mx = 0;\n        for (int row = 0; row < n; row++) {\n            for (int col = 0; col < n; col++) {\n                if (grid[row][col] == 1) continue;\n                int dr[] = { -1, 0, 1, 0};\n                int dc[] = {0, -1, 0, 1};\n                set<int> components;\n                for (int ind = 0; ind < 4; ind++) {\n                    int newr = row + dr[ind];\n                    int newc = col + dc[ind];\n                    if (isValid(newr, newc, n)) {\n                        if (grid[newr][newc] == 1) {\n                            components.insert(ds.findUPar(newr * n + newc));\n                        }\n                    }\n                }\n                int sizeTotal = 0;\n                for (auto it : components) {\n                    sizeTotal += ds.size[it];\n                }\n                mx = max(mx, sizeTotal + 1);\n            }\n        }\n        for (int cellNo = 0; cellNo < n * n; cellNo++) {\n            mx = max(mx, ds.size[ds.findUPar(cellNo)]);\n        }\n        return mx;\n        \n    }\n};\n```
['C++']