827

class Solution {
public:
    int rows, cols;
    int floodFill(vector<vector<int>> &grid, int r, int c, int col){
        if(r<0 || r>=rows || c<0 || c>=cols || grid[r][c] != 1) return 0;
        grid[r][c] = col;
        int area=1;
        area += floodFill(grid, r+1, c, col);
        area += floodFill(grid, r-1, c, col);
        area += floodFill(grid, r, c+1, col);
        area += floodFill(grid, r, c-1, col);
        return area;
    }

    int largestIsland(vector<vector<int>>& grid) {
        rows=grid.size(), cols=grid[0].size();
        unordered_map<int, int> colorMap;
        int currCol = 2;
        int maxArea = 0;
        for(int i=0; i<rows; i++)
            for(int j=0; j<cols; j++){
                if(grid[i][j] == 1){
                    colorMap[currCol] = floodFill(grid, i, j, currCol);
                    maxArea = max(maxArea, colorMap[currCol]);
                    currCol++;
                }
            }
        for(int i=0; i<rows; i++)
            for(int j=0; j<cols; j++){
                if(grid[i][j] != 0) continue;
                unordered_map<int, int> m;
                if(i-1 >= 0){
                    if(grid[i-1][j] != 0)
                        m[grid[i-1][j]] = colorMap[grid[i-1][j]];
                }
                if(j-1 >= 0){
                    if(grid[i][j-1] != 0)
                        m[grid[i][j-1]] = colorMap[grid[i][j-1]];
                }
                if(j+1 < cols){
                    if(grid[i][j+1] != 0)
                        m[grid[i][j+1]] = colorMap[grid[i][j+1]];
                }
                if(i+1 < rows){
                    if(grid[i+1][j] != 0)
                        m[grid[i+1][j]] = colorMap[grid[i+1][j]];
                }
                int area = 1;
                for(auto it=m.begin(); it != m.end(); it++){
                    area += it->second;
                }
                maxArea = max(maxArea, area);
            }
        return maxArea;
    }
};