<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

class Solution:
    def getNeighbors(self, grid, current_point):
        row, column = current_point
        candidates = [
            (row-1, column),
            (row+1, column),
            (row, column-1),
            (row, column+1)
        ]

        neighbors = []
        for candidate in candidates:
            if candidate in self.visited:
                continue

            candidate_row, candidate_column = candidate
            if candidate_row < 0 or candidate_row >= len(grid) or candidate_column < 0 or candidate_column >= len(grid[0]):
                continue
            
            if grid[candidate_row][candidate_column] == 1:
                neighbors.append(candidate)
        
        return neighbors

    def getNeighboringIslands(self, grid, row, column):
        candidates = [
            (row-1, column),
            (row+1, column),
            (row, column-1),
            (row, column+1)
        ]

        neighboring_islands = set()

        for candidate in candidates:
            if candidate in self.coords_to_island:
                neighboring_islands.add(self.coords_to_island[candidate])
        
        return neighboring_islands

    def bfs(self, grid, row_index, column_index, island_index):
        queue = deque([(row_index, column_index)])
        island_size = 0

        while len(queue) != 0:
            current_point = queue.popleft()
            current_row, current_column = current_point

            self.coords_to_island[current_point] = island_index
            self.visited.add(current_point)
            island_size += 1

            for neighbor in self.getNeighbors(grid, current_point):
                self.visited.add(neighbor)
                queue.append(neighbor)
            
        return island_size

    def largestIsland(self, grid: List[List[int]]) -> int:
        self.visited = set()
        self.coords_to_island = {}
        self.islands_to_sizes = {}
        island_index = 0

        for row_index in range(len(grid)):
            for column_index in range(len(grid[row_index])):
                if (row_index, column_index) not in self.visited and grid[row_index][column_index] == 1:
                    island_size = self.bfs(grid, row_index, column_index, island_index)
                    self.islands_to_sizes[island_index] = island_size
                    island_index += 1

        max_island_size = 0
        
        for row_index in range(len(grid)):
            for column_index in range(len(grid[row_index])):
                if grid[row_index][column_index] == 0:
                    neighboring_islands = self.getNeighboringIslands(grid, row_index, column_index)
                    total_island_size = sum([self.islands_to_sizes[island] for island in neighboring_islands]) + 1
                    max_island_size = max(max_island_size, total_island_size)
                elif grid[row_index][column_index] == 1:
                    total_island_size = self.islands_to_sizes[self.coords_to_island[(row_index, column_index)]]
                    max_island_size = max(max_island_size, total_island_size)

        return max_island_size
48193