✅ Making a large island | Detailed Explanation | Java
Intuition\n The idea is to find all the distinct regions(islands) in the grid. We name these regions with a number starting from 2 (Since 0,1 are reserved for t
**Intuition**\n* The idea is to find all the distinct regions(islands) in the grid. We name these regions with a number starting from `2` (Since `0`,`1` are reserved for the grid). Then we apply the flood fill algorithm with the regions.\n* While applying flood fill algorithm we need to also get the area of the region and store it. So we can use a map to get area of any region.\n* Once we have marked all the regions what should we do. The problem we have to solve now is merge multiple islands if there is just one `0` separating these.\n* So we have to iterate over all the `0`s and check the distinct neighbors. Now all these neighbors will become one island if we flip this `0` to `1`. So we add the area for all the neighbors.\n* If this area is greater than the max area, we update the max.\n\n```\nclass Solution {\n    public int largestIsland(int[][] grid) {\n        Map<Integer, Integer> regionsArea = new HashMap<>();\n        regionsArea.put(0,0);\n        \n        int n = grid.length;\n        int region = 2;\n        for(int i=0;i<n;i++){\n            for(int j=0;j<n;j++){\n                if(grid[i][j]==1){\n                    int area = floodFill(grid, i, j, region);\n                    regionsArea.put(region, area);\n                    region++;\n                }\n            }\n        }\n        \n        int max = regionsArea.getOrDefault(2,0);\n        for(int r=0;r<n;r++){\n            for(int c=0;c<n;c++){\n                if(grid[r][c]==0){\n                    Set<Integer> neighbors = new HashSet<>();\n                    neighbors.add(r>0?grid[r-1][c]:0);\n                    neighbors.add(c>0?grid[r][c-1]:0);\n                    neighbors.add(r<n-1?grid[r+1][c]:0);\n                    neighbors.add(c<n-1?grid[r][c+1]:0);\n                    int area = 1;\n                    for(int neighbor: neighbors){\n                        area+=regionsArea.get(neighbor);\n                    }\n                    if(area>max){\n                        max = area;\n                    }\n                }\n            }\n        }\n        \n        return max;\n    }\n    \n    public int floodFill(int[][] grid, int r, int c, int region) {\n        int n = grid.length;\n        if(r<0||r>=n||c<0||c>=n||grid[r][c]!=1){\n            return 0;\n        }\n        \n        grid[r][c] = region;\n        \n        int sum = 1;\n        sum+=floodFill(grid, r, c+1, region);\n        sum+=floodFill(grid, r+1, c, region);\n        sum+=floodFill(grid, r, c-1, region);\n        sum+=floodFill(grid, r-1, c, region);\n        \n        return sum;\n    }\n}\n```\n\n**Please upvote if this solution helps you so that it can reach others. Cheers :)**
['Depth-First Search', 'Breadth-First Search', 'Java']