DFS C++ intuitive solution with explanation, O(n*n)
Let us group the islands by changing the 1s to their index and increment the index.\nAll islands in a particular group have the same index. We store the index a
Let us group the islands by changing the 1s to their index and increment the index.\nAll islands in a particular group have the same index. We store the index and the corresponding area in a map and keep track of the maximum area until now.\nExamples:\n1 0 1 -> 2 0 3    \n0 1 1 -> 0 3 3 \n1 0 1 ->  4 0 3\n\nNow, we traverse each 0 in the grid and find its adjacent group and add up their areas. \nFor the 0 at (0,1), we get area=m[2]+m[3]+1=1+4+1=6\nFor the 0 at (1,0), we get area=m[2]+m[3]+m[4]+1=1+4+1+1=7\nWe add 1 to account for the converted island.\n\nAt the end, we are left with the required answer.\n\n```\nclass Solution {\npublic:\n    int dfs(vector<vector<int>>& grid, int i, int j, int index) {\n        int n=grid.size();\n        if(i<0 || i>=n || j<0 || j>=n || grid[i][j]!=1) return 0;\n        grid[i][j]=index;\n        int count = dfs(grid, i+1, j, index) + \n                    dfs(grid, i-1, j, index) + \n                    dfs(grid, i, j+1, index) + \n                    dfs(grid, i, j-1, index);\n        return count+1;\n    }\n    \n    void findNeighbours(vector<vector<int>>& grid, int i, int j, set<int>& s) {\n\t\t//finding adjacent island groups\n        int n=grid.size();\n        if(i>0) s.insert(grid[i-1][j]);\n        if(j>0) s.insert(grid[i][j-1]);\n        if(i<n-1) s.insert(grid[i+1][j]);\n        if(j<n-1) s.insert(grid[i][j+1]);\n    }\n    \n    int largestIsland(vector<vector<int>>& grid) {\n        int n=grid.size(), res=0, index=2, count;\n        map<int, int> area;\n        for(int i=0;i<n;i++) {\n            for(int j=0;j<n;j++) {\n                if(grid[i][j]==1) {\n                    area[index]=dfs(grid, i, j, index);\n                    res=max(res, area[index++]);\n\t\t\t\t\t//if the grid is one large island, we would find the maximum size island here\n                }\n            }\n        }\n\n        for(int i=0;i<n;i++) {\n            for(int j=0;j<n;j++) {\n                if(grid[i][j]==0) {\n                    set<int> s;\n                    findNeighbours(grid, i, j, s);\n                    count=1;    //to account for the converted island\n                    for(int i:s)\n                        count+=area[i];       // count the number of islands in the adjacent groups\n                    res=max(res, count);\n                }\n            }\n        }\n        \n        return res;\n    }\n};\n```
['Depth-First Search', 'C']