🐍Python BFS solution
Intuition\nBy replacing water cell to earth cell (0 -> 1) we can either increase area of nearby island by +1 or either connect nearby island by that cell. If th
# Intuition\nBy replacing water cell to earth cell (0 -> 1) we can either increase area of nearby island by +1 or either connect nearby island by that cell. If there is no nearby island, we got island of size 1.\nSo, at every water cell we calculate size of possible island `curr_size` and update max size `ans`. \n\n# Approach\nFirstly, we apply Breadth-First Search to find all islands and save size of islands in array `islands_sizes`. Moreover, we mark every visited island as `number` 2, 3, 4.. and `islands_sizes[number - 2]` is a size of island `number`. \n\nNext, we iterate over water cells. At every `0` cell, initialy `curr_size = 1`, then we check its neighbours and if it is island `number`, we increase current cell size by size of this neighbour island `islands_sizes[number - 2]`. For this step `neighbours` of current water cell is `set()`, because we have to add size of every neighbour only once.\n\n# Complexity\n- Time complexity: O(N^2)\nBFS and iterating over all water cells is N^2 + N^2.\n\n- Space complexity: O(N^2)\n`islands_sizes` in the worst case has N*N / 2 elements. So memory is O(N^2).\n\n# Code\n```\nfrom collections import deque\nclass Solution:\n    def largestIsland(self, grid: List[List[int]]) -> int:\n        i = 0 \n        j = 0\n        n = len(grid)\n        islands_sizes = []\n        \n\n        def vertex_neighb(coord_i, coord_j):\n            neighbours = []\n            if coord_j + 1 < n and grid[coord_i][coord_j + 1] == 1:\n                neighbours.append((coord_i, coord_j + 1))\n\n            if coord_j > 0 and grid[coord_i][coord_j - 1] == 1:\n                neighbours.append((coord_i, coord_j - 1))\n\n            if coord_i + 1 < n and grid[coord_i + 1][coord_j] == 1:\n                neighbours.append((coord_i + 1, coord_j))\n\n            if coord_i > 0 and grid[coord_i - 1][coord_j] == 1:\n                neighbours.append((coord_i - 1, coord_j))\n\n            return neighbours\n\n        for i in range(n):\n            for j in range(n):\n                que = deque([(i, j)])\n                \n                if grid[i][j] == 1:\n                    islands_sizes.append(1)\n                    while que:\n                        vertex = que.popleft()\n                        grid[vertex[0]][vertex[1]] = len(islands_sizes) + 1\n                        \n                        for neighb in vertex_neighb(vertex[0], vertex[1]):\n                            grid[neighb[0]][neighb[1]] = len(islands_sizes) + 1\n                            islands_sizes[-1] += 1\n                            que.append((neighb[0], neighb[1]))\n\n        if islands_sizes:    \n            ans = max(islands_sizes)\n        else:\n            ans = 0\n         \n        for i in range(n):\n            for j in range(n):\n                if grid[i][j] == 0:\n                    neighbours = set()\n                    if j + 1 < n and grid[i][j + 1] != 0:\n                        neighbours.add(grid[i][j + 1])\n\n                    if j > 0 and grid[i][j - 1] != 0:\n                        neighbours.add(grid[i][j - 1])\n\n                    if i + 1 < n and grid[i + 1][j] != 0:\n                        neighbours.add(grid[i + 1][j])\n\n                    if i > 0 and grid[i - 1][j] != 0:\n                        neighbours.add(grid[i - 1][j])\n                    curr_size = 1\n                    for neighb in neighbours:\n                        curr_size += islands_sizes[neighb - 2]\n                    \n                    ans = max(ans, curr_size)\n\n        return ans\n\n```
['Breadth-First Search', 'Python3']