from collections import defaultdict

class Solution:
    def __init__(self):
        self.island_id = 2
        self.island_id_to_area = defaultdict(int)

    def largestIsland(self, grid: List[List[int]]) -> int:
        self.grid = grid
        max_area = 0

        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if self.grid[i][j] == 1:
                    self.depth_first_search(i, j)
                    self.island_id += 1

        has_water = False

        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if self.grid[i][j] == 0:
                    has_water = True
                    max_area = max(max_area, self.combined_islands_area(i, j))

        if not has_water:
            return len(grid) * len(grid[0])

        return max_area
    
    def depth_first_search(self, i, j):
        if i < 0 or j < 0 or i >= len(self.grid) or j >= len(self.grid[0]):
            return

        if self.grid[i][j] != 1:
            return

        self.grid[i][j] = self.island_id
        self.island_id_to_area[self.island_id] += 1

        for a, b in [
            (-1, 0),
            (0, -1), (0, 1),
            (1, 0)
        ]:
            m = i + a
            n = j + b
            self.depth_first_search(m, n)
    
    def combined_islands_area(self, i, j):
        island_ids = set()

        for a, b in [
            (-1, 0),
            (0, -1), (0, 1),
            (1, 0)
        ]:
            m = i + a
            n = j + b

            if m < 0 or n < 0 or m >= len(self.grid) or n >= len(self.grid[0]):
                continue

            if self.grid[m][n] != 0:
                island_ids.add(self.grid[m][n])
        
        area = 1

        for island_id in island_ids:
            area += self.island_id_to_area[island_id]

        return area