Python short DFS w/ Explanation
The idea is to do a dfs and name the Islands based on component number and also store each Island\'s size.\n\nThe next step is to simply iterate through the gri
The idea is to do a dfs and name the Islands based on component number and also store each Island\'s size.\n\nThe next step is to simply iterate through the grid, and for each 0, find the maximum number of components it can unite and add up their sizes + 1\n```\n    def largestIsland(self, grid):\n        def dfs(i, j, comps):\n            if not (0 <= i < len(grid) and 0 <= j < len(grid[0]) and grid[i][j] == 1): return 0\n            grid[i][j] = comps\n            return 1 + sum([dfs(i+dir[0], j+dir[1], comps)for dir in dirs])\n        comps = 2\n        dirs = [(-1, 0), (1, 0), (0, -1), (0, 1)]\n        comp_sizes = {}\n        for i in range(len(grid)):\n            for j in range(len(grid[0])):\n                if grid[i][j] == 1:\n                    size = dfs(i, j, comps)\n                    comp_sizes[comps] = size\n                    comps += 1\n\n        res = 0\n        zeroes_present = False\n        for i in range(len(grid)):\n            for j in range(len(grid[0])):\n                resij = 0\n                if grid[i][j] == 0:\n                    zeroes_present = True\n                    for comp in set([grid[i+dir[0]][j+dir[1]] for dir in dirs if (0 <= i+dir[0] < len(grid) and 0 <= j+dir[1] < len(grid[0]) and grid[i+dir[0]][j+dir[1]] != 0)]):\n                        resij += comp_sizes[comp]\n                res = max(res, resij)\n\n        return len(grid) * len(grid[0]) if not zeroes_present else res+1\n```
[]