JAVA STEP BY STEP EXPLAINED SOLUTION
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)$$ -->O(N^2)\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->O(N^2)\n![Screenshot_20230205_171246.png](https://assets.leetcode.com/users/images/d7dde3a3-4783-446f-ab54-600273116048_1694931365.0964365.png)\n\n\n# Code\n```\nclass DisjointSet {\n    List<Integer> rank = new ArrayList<>();\n    List<Integer> parent = new ArrayList<>();\n    List<Integer> size = new ArrayList<>();\n\n    public DisjointSet(int n) {\n        // Initialize disjoint set data structure with n nodes\n        for (int i = 0; i <= n; i++) {\n            rank.add(0);       // Initialize rank of each node to 0\n            parent.add(i);     // Initialize parent of each node to itself\n            size.add(1);       // Initialize size of each component to 1\n        }\n    }\n\n    public int findUPar(int node) {\n        // Find the ultimate parent of a node\n        if (node == parent.get(node)) {\n            return node;    // Node is its own parent, return itself\n        }\n        int ulp = findUPar(parent.get(node)); // Recursively find the ultimate parent\n        parent.set(node, ulp); // Path compression - set parent to the ultimate parent\n        return parent.get(node);\n    }\n\n    public 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; // They are already in the same component\n        if (size.get(ulp_u) < size.get(ulp_v)) {\n            // Attach the smaller component (ulp_u) to the larger component (ulp_v)\n            parent.set(ulp_u, ulp_v);\n            size.set(ulp_v, size.get(ulp_v) + size.get(ulp_u)); // Update the size\n        } else {\n            // Attach the smaller component (ulp_v) to the larger component (ulp_u)\n            parent.set(ulp_v, ulp_u);\n            size.set(ulp_u, size.get(ulp_u) + size.get(ulp_v)); // Update the size\n        }\n    }\n}\n\nclass Solution {\n    private boolean isValid(int adjr, int adjc, int n){\n        return adjr >= 0 && adjr < n && adjc >= 0 && adjc < n;\n    }\n\n    public int largestIsland(int[][] grid) {\n\n        int n = grid.length;\n        DisjointSet ds = new DisjointSet(n * n);\n\n        // Build the disjoint set based on the grid\n        for(int row = 0; row < n; row++){\n            for(int col = 0; col < n; col++){\n                if(grid[row][col] == 0) continue;\n\n                int dr[] = {-1, 0, 1, 0};\n                int dc[] = {0, -1, 0, 1};\n\n                for(int ind = 0; ind < 4; ind++){\n                    int newr = row + dr[ind];\n                    int newc = col + dc[ind];\n\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        int mx = 0;\n\n        // Traverse the grid to find the largest island size\n        for(int row = 0; row < n; row++){\n            for(int col = 0; col < n; col++){\n                if(grid[row][col] == 1) continue;\n\n                int dr[] = {-1, 0, 1, 0};\n                int dc[] = {0, -1, 0, 1};\n\n                HashSet<Integer> components = new HashSet<>();\n                for(int ind = 0; ind < 4; ind++){\n                    int newr = row + dr[ind];\n                    int newc = col + dc[ind];\n\n                    if(isValid(newr,newc,n) && grid[newr][newc] == 1){\n                        if(grid[newr][newc] == 1){\n                            components.add(ds.findUPar(newr * n + newc));\n                        }\n                    }\n                }\n                int sizeTotal = 0;\n\n                for(Integer parents: components){\n                    sizeTotal += ds.size.get(parents);\n                }\n                mx = Math.max(mx, sizeTotal + 1); // Add 1 for the current cell\n            }\n        }\n\n        // Find the maximum component size in the disjoint set\n        for(int cellNo = 0; cellNo < n; cellNo++){\n            mx = Math.max(mx, ds.size.get(ds.findUPar(cellNo)));\n        }\n        return mx; // Return the largest island size\n    }\n}\n\n```
['Array', 'Breadth-First Search', 'Union Find', 'Matrix', 'Java']