<p>You are given an <code>n x n</code> binary matrix <code>grid</code>. You are allowed to change <strong>at most one</strong> <code>0</code> to be <code>1</code>.</p>

<p>Return <em>the size of the largest <strong>island</strong> in</em> <code>grid</code> <em>after applying this operation</em>.</p>

<p>An <strong>island</strong> is a 4-directionally connected group of <code>1</code>s.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> grid = [[1,0],[0,1]]
<strong>Output:</strong> 3
<strong>Explanation:</strong> Change one 0 to 1 and connect two 1s, then we get an island with area = 3.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> grid = [[1,1],[1,0]]
<strong>Output:</strong> 4
<strong>Explanation: </strong>Change the 0 to 1 and make the island bigger, only one island with area = 4.</pre>

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> grid = [[1,1],[1,1]]
<strong>Output:</strong> 4
<strong>Explanation:</strong> Can&#39;t change any 0 to 1, only one island with area = 4.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>n == grid.length</code></li>
	<li><code>n == grid[i].length</code></li>
	<li><code>1 &lt;= n &lt;= 500</code></li>
	<li><code>grid[i][j]</code> is either <code>0</code> or <code>1</code>.</li>
</ul>


class Solution:
    def largestIsland(self, grid: List[List[int]]) -> int:
        # Find the size of each existing component. For each connected component,
        # record the total size and a set of the coordinates contained.
        # For each 0, check whether each of its neighbors = 1.
        # If so, check which connected component it belongs to and add the size.

        visited = set() # set of tuple coordinates
        connected_components = [] # set of (size, coordinates)

        # print("initial grid", grid)

        for r in range(len(grid)):
            for c in range(len(grid[r])):
                if (r, c) not in visited and grid[r][c]:
                    coords = []
                    # print("traversing", (r, c))
                    self.connected_component(visited, (r, c), coords, grid)
                    connected_components += [(len(coords), coords)]
        
        component_map = dict() # coord -> component id
        for i in range(len(connected_components)):
            # print(connected_components[i])
            component_id, components = connected_components[i]
            for c in components:
                component_map[c] = i
        
        if not connected_components:
            return 1
            
        largest_island = max(len(components) for _, components in connected_components)

        for r in range(len(grid)):
            for c in range(len(grid)):
                if not grid[r][c]:
                    join_components = set()
                    if (r - 1, c) in component_map:
                        join_components.add(component_map[(r - 1, c)])
                    if (r, c + 1) in component_map:
                        join_components.add(component_map[(r, c + 1)])
                    if (r + 1, c) in component_map:
                        join_components.add(component_map[(r + 1, c)])
                    if (r, c - 1) in component_map:
                        join_components.add(component_map[(r, c - 1)])
                    # print([len(connected_components[c_id][1]) for c_id in join_components])
                    size = sum([len(connected_components[c_id][1]) for c_id in join_components]) + 1
                    if size > largest_island:
                        largest_island = size
        return largest_island

    def connected_component(self, visited, current_coord, coords, grid):
        r, c = current_coord
        if grid[r][c] and current_coord not in visited:
            coords += [current_coord]
            visited.add(current_coord)
            if r > 0 and (r - 1, c) not in visited and grid[r - 1][c]:
                self.connected_component(visited, (r - 1, c), coords, grid)
            if c < len(grid) - 1 and (r, c + 1) not in visited and grid[r][c + 1]:
                self.connected_component(visited, (r, c + 1), coords, grid)
            if r < len(grid) - 1 and (r + 1, c) not in visited and grid[r + 1][c]:
                self.connected_component(visited, (r + 1, c), coords, grid)
            if c > 0 and (r, c - 1) not in visited and grid[r][c - 1]:
                self.connected_component(visited, (r, c - 1), coords, grid)

50331