human
I found an interesting problem on https://leetcode.com/problems/making-a-large-island/:
In a 2D grid of 0s and 1s, we change at most one 0 to a 1.
After, what is the size of the largest island? (An island is a 4-directionally connected group of 1s).
Example 1:
Input: [[1, 0], [0, 1]]
Output: 3
Explanation: Change one 0 to 1 and connect two 1s, then we get an island with area = 3.

Example 2:
Input: [[1, 1], [1, 0]]
Output: 4
Explanation: Change the 0 to 1 and make the island bigger, only one island with area = 4.
Example 3:
Input: [[1, 1], [1, 1]]
Output: 4
Explanation: Can't change any 0 to 1, only one island with area = 4.
 
Notes:

1 <= grid.length = grid[0].length <= 50.
0 <= grid[i][j] <= 1.

I tried it in Python, but could not do it. Can you solve it?

 Write me a the size of the largest island?
assistant
#Here is the size of the largest island.

DIRECTIONS = [(0, 1), (0, -1), (1, 0), (-1, 0)]
class Solution:
    def largestIsland(self, grid: List[List[int]]) -> int:
        N = len(grid)
        
        def move(x, y):
            ans = []
            for mv_x, mv_y in DIRECTIONS:
                x_ = x + mv_x
                y_ = y + mv_y
                if 0 <= x_ < N and 0 <= y_ < N:
                    ans.append((x_, y_))
            return ans
        
        # return area of the island
        def dfs(x, y, idx):
            ans = 1
            grid[x][y] = idx
            for i, j in move(x, y):
                if grid[i][j] == 1:
                    ans += dfs(i, j, idx)
            return ans
        
        idx = 2
        areas = {0: 0}
        for i in range(N):
            for j in range(N):
                if grid[i][j] == 1:
                    areas[idx] = dfs(i, j, idx)
                    idx += 1
        
        ans = max(areas.values())
        for i in range(N):
            for j in range(N):
                if grid[i][j] == 0:
                    cands = set(grid[x][y] for x, y in move(i, j))
                    ans = max(ans, sum(areas[idx] for idx in cands) + 1)
        return ans