<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>

from collections import deque, defaultdict
class Solution:
    def is_inbounds(self, coord: tuple, grid_len: int):
        return coord[0] >= 0 and coord[0] < grid_len and coord[1] >= 0 and coord[1] < grid_len
    
    def get_neighbors(self, coord: tuple, grid_len: int):
        row = coord[0]
        col = coord[1]

        neighbors = []
        neighbor_candidates = [
            (row + 1, col),
            (row - 1, col),
            (row, col -1),
            (row, col + 1)
        ]
        for candidate in neighbor_candidates:
            if self.is_inbounds(candidate, grid_len):
                neighbors.append(candidate)
        return neighbors



    def get_clusters(self, grid: List[List[int]]) -> int:
        grid_len = len(grid)
        visited = dict()
        clusters = []
        for i in range(0, grid_len):
            for j in range(0, grid_len):
                if (i, j) in visited:
                    continue
                elif grid[i][j] == 0:
                    visited[(i,j)] = True
                    continue
                else:
                    to_visit = deque([(i, j)])
                    visited[(i, j)] = True
                    curr_cluster = [(i, j)]
                    while len(to_visit) > 0:
                        top = to_visit.popleft()
                        neighbors = self.get_neighbors(top, grid_len)
                        for neighbor in neighbors:
                            if neighbor not in visited and grid[neighbor[0]][neighbor[1]] == 1:
                                visited[neighbor] = True
                                curr_cluster.append(neighbor)
                                to_visit.append(neighbor)
                        
                    clusters.append(curr_cluster)
        return clusters

    def largestIsland(self, grid: List[List[int]]) -> int:
        boundaries = defaultdict(list)
        all_clusters = self.get_clusters(grid)
        grid_len = len(grid)

        for cluster in all_clusters:
            cluster_neighbors = set()
            for point in cluster:
                point_neighbors = self.get_neighbors(point, grid_len)
                for neighbor in point_neighbors:
                    if grid[neighbor[0]][neighbor[1]] == 0:
                        cluster_neighbors.add(neighbor)
            for cluster_neighbor in cluster_neighbors:
                boundaries[cluster_neighbor].append(cluster)
        
        max_island_cluster = None
        for boundary_point, clusters in boundaries.items():
            total_cluster_length = 0
            for cluster in clusters:
                for point in cluster:
                    total_cluster_length+=1
            if max_island_cluster is None:
                max_island_cluster = (boundary_point, total_cluster_length)
            elif total_cluster_length > max_island_cluster[1]:
                max_island_cluster = (boundary_point, total_cluster_length)


        if max_island_cluster is None:
            # Handle no boundaries
            max_cluster_size = 0
            for cluster in all_clusters:
                if len(cluster) > max_cluster_size:
                    max_cluster_size = len(cluster)
            return max_cluster_size if max_cluster_size > 0 else 1
        else:
            return max_island_cluster[1] + 1
72418