#define vi vector<int>
#define vb vector<bool>
#define ss second

class Solution {
    int n,m;
    int row[4]={1,-1,0,0},col[4]={0,0,1,-1};
public:
    int largestIsland(vector<vi>& grid) {

        n=grid.size();
        unordered_map<int,int> mp;
        mp=maxAreaOfIsland(grid);

        int maxArea=0;
        for(auto i:mp)
            maxArea=i.ss>maxArea?i.ss:maxArea;

        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                if(grid[i][j]==0)
                    maxArea=max(maxArea,findAdjMaxArea(grid,i,j,mp));
            }
        }

        return maxArea;
    }

    int findAdjMaxArea(vector<vi>& grid,int i,int j,unordered_map<int,int> mp){

        int maxArea=0;
        set<int> mySet;
        for(int k=0;k<4;k++){
            int x=i+row[k],y=j+col[k];
            if(x>=0 && y>=0 && x<n && y<n && grid[x][y] != 0)
                mySet.insert(grid[x][y]);
        }

        for(int i:mySet){
            maxArea+=mp[i];
        }
        return maxArea+1;
    }
    unordered_map<int,int> maxAreaOfIsland(vector<vi>& grid) {

        m=grid.size(),n=grid[0].size();
        unordered_map<int,int> mp;
        //vector<vb> visited(m,vb(n,false));
        int gridId=2;

        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                if(grid[i][j]==1){
                    int area=calMaxArea(grid,i,j,gridId);
                    mp[gridId]=area;
                    gridId++;
                }
            }
        }

        return mp;
    }
    int calMaxArea(vector<vi>& grid,int i,int j,int gridId){

        //base case
        if (i<0 || j<0 || i>=m || j>=n || grid[i][j] != 1)  return 0;

        grid[i][j]=gridId;
        int maxArea=0;

        for(int k=0;k<4;k++){
            int x=i+row[k],y=j+col[k];
            maxArea+=calMaxArea(grid,x,y,gridId);
        }
        return maxArea+1;
    }
};