You are given an n x n binary matrix grid. You are allowed to change at most one 0 to be 1.

Return the size of the largest island in grid after applying this operation.

An island is a 4-directionally connected group of 1s.

&nbsp;
Example 1:

Input: grid = [[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: grid = [[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: grid = [[1,1],[1,1]]
Output: 4
Explanation: Can't change any 0 to 1, only one island with area = 4.


&nbsp;
Constraints:


	n == grid.length
	n == grid[i].length
	1 &lt;= n &lt;= 500
	grid[i][j] is either 0 or 1.

class Solution:
    def largestIsland(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        # parent array to keey track
        parent = list(range(m*n))
        # rank array used for union by rank and size calculation
        rank = [1 for _ in range(m*n)]
        
        # standard DSU find function
        def find(x):
            while x != parent[x]:
                parent[x] = parent[parent[x]]
                x = parent[x]
            return x
        
        # standard DSU union by rank function
        def union(x,y):
            parX, parY = find(x), find(y)
            if parX == parY: return
            if rank[parX] >= rank[parY]:
                rank[parX] += rank[parY]
                parent[parY] = parX
            else:
                rank[parY] += rank[parX]
                parent[parX] = parY
    
        # Step 1: join the land

        # for each island we perform union operation
        for i, row in enumerate(grid):
            for j, val in enumerate(row):
                
                # important condition: if we have a water body, we set its rank to 0 (will be used in the next step)
                if not val: 
                    rank[i*m+j] = 0
                    continue
                
                # performing union of land bodies
                for x,y in [(i-1, j),(i+1, j),(i, j+1),(i, j-1)]:
                    # outside of grid check
                    if not (0 <= x < m and 0 <= y < n): continue
                    
                    if grid[x][y]: union(i*m+j, x*m+y)
        
        # Step 2: convert a water body (if present)
        
        # the minimum final ans will always be the size of the largest land present 
        ans = max(rank)
        for i, row in enumerate(grid):
            for j, val in enumerate(row):
                
                # we dont need to do anything if we encounter a land
                if val: continue
                
                neighbours = set()
                res = 0
                
                # 
                for x,y in [(i-1, j),(i+1, j),(i, j+1),(i, j-1)]:
                    # outside of grid check
                    if not (0 <= x < m and 0 <= y < n): continue
                        
                    # checking unique neighbours by adding the parent to the set
                    # here we dont care if the neighbour is water as its rank is 0 so it contributes nothing
                    idx = x*m+y
                    neighbours.add(find(idx))
                
                # Once we have all unique neighbours, just add their ranks
                for idx in neighbours:
                    res += rank[idx]
                
                # res + 1 because we convert the current cell (i,j) to land too
                ans = max(ans, res+1)
        
        return ans
class Solution {
    int dir[][] = new int[][]{
        {1, 0},
        {-1,0},
        {0,1},
        {0,-1}
    };
    private int countArea(int grid[][], int i, int j, int num){
        if(i < 0 || i >= grid.length || j < 0 || j >= grid[0].length)
            return 0;
        
        if(grid[i][j] != 1) return 0;
        
        grid[i][j] = num;
        int count = 0;
        for(int d[] : dir){
            count += countArea(grid, i + d[0], j + d[1], num);
        }
        
        return 1 + count;
    }
    
    private void fillDP(int grid[][], int dp[][], int i, int j, int count, int num){
        if(i < 0 || i >= grid.length || j < 0 || j >= grid[0].length) return ;
        
        if(grid[i][j] != num) return;
        
        if(dp[i][j] != 0) return ;
        dp[i][j] = count;
        for(int d[] : dir){
            fillDP(grid, dp, i + d[0], j + d[1], count, num);
        }
        
    }
    
    
    public int largestIsland(int[][] grid) {
        int n = grid.length, m = grid[0].length;
        int dp[][] = new int[n][m];
        
        int num = 1;
        for(int i = 0; i < n; ++i){
            for(int j = 0; j < m; ++j){
                if(grid[i][j] == 1){
                    ++num;
                    int count1 = countArea(grid, i, j, num);
                    fillDP(grid, dp, i, j, count1, num);
                }
            }
        }
        
        int max = 0;
        for(int i = 0; i < n; ++i){
            for(int j = 0; j < m; ++j){
                if(grid[i][j] != 0) continue;
                int val = 1;
                Set<Integer> set = new HashSet<>();
                for(int d[] : dir){
                    int newRow = i + d[0];
                    int newCol = j + d[1];
                    
                    if(newRow < 0 || newRow >= n || newCol < 0 || newCol >= m) continue;
                    if(set.contains(grid[newRow][newCol])) continue;
                    
                    val += dp[newRow][newCol];
                    set.add(grid[newRow][newCol]);
                }
                max = Math.max(max, val);
            }
        }
        
        if(max == 0) return n * m;
        return max;
        
    }
}
class Solution {
    int dir[4][2]={{0,1},{1,0},{-1,0},{0,-1}};
    
    bool isValid(vector<vector<int>>const &grid,vector<vector<int>> &visited, int row, int col){
        int n=grid.size();
        
        if(row<0 || row>=n || col<0 || col>=n || grid[row][col]!=1 || visited[row][col]!=0){
            return false;
        }
        return true;
    }
    
    int helper(vector<vector<int>>const &grid,vector<vector<int>> &visited, int row, int col){
        
        if(!isValid(grid,visited,row,col)) return 0;
        
        visited[row][col]=1;
            
       
           
       return 1+helper(grid,visited, row+dir[0][0], col+dir[0][1])+
                helper(grid,visited, row+dir[1][0], col+dir[1][1])+
                helper(grid,visited, row+dir[2][0], col+dir[2][1])+
                helper(grid,visited, row+dir[3][0], col+dir[3][1]);
        
        return 0;
    }
public:
    int largestIsland(vector<vector<int>>& grid) {
        int ans=0;
        int n=grid.size();
        for(int i=0;i<n;i++){
            for(int j=0;j<grid.size();j++){
                
                if(grid[i][j]==0){
                    grid[i][j]=1;
                    vector<vector<int>> visited(n,vector<int>(n,0));
                    ans=max(ans,helper(grid,visited, i,j));
                    grid[i][j]=0;
                }
                
            }
        }
        return ans==0?n*n:ans;
    }
};
var largestIsland = function(grid) {
    const n = grid.length
	/**
	 *  Create the merge find (union find) structure --> https://www.youtube.com/watch?v=ibjEGG7ylHk
	 *  For this case, we will form the sets at once, already assigning the same representative to all members.
	 *  Thus, we can use this simplistic implementation without path compression and find(i) = mf[i]
	 */
    const mf = []
    for (let i = 0; i < n*n; i++) {
        mf.push(i)
    }
	// Helper that converts coordinates to array position
    const toPos = (r, c) => r * n + c
	// Recursively set the merge find structure to represent the islands' map
    const merge = (r, c, repr) => {
        mf[toPos(r, c)] = repr // Merge coordinate
		/**
		 *  Visit neighbors. To visit a neighboring coordinate we first check for:
		 *  Boundaries (coordinates stay within matrix limits)
		 *  Neighbor is land (contains a 1)
		 *  We didn't visit it already (has different representative)
		 */
        if (r > 0 && grid[r-1][c] === 1 && mf[toPos(r-1, c)] !== repr) { // Top
            merge(r-1, c, repr)
        }
        if (c < n-1 && grid[r][c+1] === 1 && mf[toPos(r, c+1)] !== repr) { // Right
            merge(r, c+1, repr)
        }
        if (r < n-1 && grid[r+1][c] === 1 && mf[toPos(r+1, c)] !== repr) { // Bottom
            merge(r+1, c, repr)
        }
        if (c > 0 && grid[r][c-1] === 1 && mf[toPos(r, c-1)] !== repr) { // Left
            merge(r, c-1, repr)
        }
    }
	/**
	 *  For each land (1) position that wasn't already merged into a set,
	 *  we define a new set with its neighbors.
	 */
    for (let i = 0; i < n; i++) {
        for (let j = 0; j < n; j++) {
            const pos = toPos(i, j)
            if (grid[i][j] === 1 && mf[pos] === pos) {
                merge(i, j, pos)
            } 
        }
    }
	/**
	 *  We can now calculate the surface of every island by counting the number of cells
	 *  with the same representative.
	 */
    const count = Array(n*n).fill(0)
    mf.forEach(el => count[el]++)
    /**
	 *  Now we have to decide on which sea (0) should be toggled into land (1).
	 *  For this we save, for each zero, which sets it is contact with. Once this is done,
	 *  we can calculate the entire surface by suming 1 + the surface of all touching sets.
	 *  Again, to add the neighbor set to the store, we need to check that it is a one, that we
	 *  are within the boundaries, and that it was not already marked as neighbor.
	 *  We store the maximum surface found, which is the final solution.
	 */
    let maxSurface = 0
    for (let r = 0; r < n; r++) {
        for (let c = 0; c < n; c++) {
            if (grid[r][c] === 0) {
                const touching = []
                let currentSurface = 1
                if (r > 0 && grid[r-1][c] === 1 && !touching.includes(mf[toPos(r-1, c)])) { // Top
                    touching.push(mf[toPos(r-1,c)])
                }
                if (c < n-1 && grid[r][c+1] === 1 && !touching.includes(mf[toPos(r, c+1)])) { // Right
                    touching.push(mf[toPos(r,c+1)])
                }
                if (r < n-1 && grid[r+1][c] === 1 && !touching.includes(mf[toPos(r+1, c)])) { // Bottom
                    touching.push(mf[toPos(r+1, c)])
                }
                if (c > 0 && grid[r][c-1] === 1 && !touching.includes(mf[toPos(r, c-1)])) { // Left
                    touching.push(mf[toPos(r, c-1)])
                }
                touching.forEach(set => currentSurface += count[set])
                if (currentSurface > maxSurface) {
                    maxSurface = currentSurface
                }
            } 
        }
    }
    /**
	 * If maxSurface remained at zero, it means the input is a matrix of ones.
	 */
    if (maxSurface > 0) { return maxSurface }
    return n*n
}
Making A Large Island