C++ , Beats 96.49% CPP user
We run simple DFS on a cell , so that we traverse the whole Island and mark that Island in the visited array as a unique value. We also remember the area realte
### We run simple DFS on a cell , so that we traverse the whole Island and mark that Island in the visited array as a unique value. We also remember the area realted to the corresponding value which represents each Island.\n\nConsider the follwing matrix -> \n\n|0|0|1|0|0|\n|-|-|-|-|-|\n|0|0|1|0|0|\n|1|0|1|0|1|\n|0|0|1|0|0|\n|1|1|0|1|1|\n\nNow if we run a dfs and mark all the island with unique values in visited array :\n|0|0|1|0|0|\n|-|-|-|-|-|\n|0|0|1|0|0|\n|2|0|1|0|3|\n|0|0|1|0|0|\n|4|4|0|5|5|\n\nAnd also store the area of the corresponding value in a separate array :\n|area|0|4|1|1|2|2|\n|-|-|-|-|-|-|-|\n|index|0|1|2|3|4|5|\n\nSo for every cell in the grid with value 0 we calculate the area by adding all the Island areas on the 4 sides , marked by underlines ->\n\n|0|<U>5</U>|1|<U>5</U>|0|\n|-|-|-|-|-|\n|<U>2</U>|<U>5</U>|1|<U>5</U>|<U>2</U>|\n|1|<U>6</U>|1|<U>6</U>|1|\n|<U>4</U>|<U>7</U>|1|<U>7</U>|<U>4</U>|\n|1|1|<U>9</U>|1|1|\n\nSo among the underlined values we return the max value.\n\nIf there are no zeroes return the size of the grid.\n\n```c++\nclass Solution {\npublic:\n    vector <pair<int,int>> dir = {{1,0},{0,1},{-1,0},{0,-1}};\n    int vis[501][501];\n    bool check(int i,int j,vector<vector<int>>& grid){\n        if(i>=0 && i<grid.size() && j>=0 && j<grid[0].size() && grid[i][j] == 1)\n            return true;\n        return false;\n    }\n    int dfs(vector<vector<int>>& grid,int i,int j,int &val){\n        int count = 1;\n        vis[i][j] = val;\n        for(auto x:dir){\n            if(check(i+x.first,j+x.second,grid) && vis[i+x.first][j+x.second] != val)\n                count += dfs(grid,i+x.first,j+x.second,val);\n        }\n        return count;\n    }\n    int largestIsland(vector<vector<int>>& grid) {\n        memset(vis,0,sizeof(vis));\n        int val = 1;\n        int dp[grid.size()*grid[0].size()+2];\n        memset(dp,0,sizeof(dp));\n        for(int i=0;i<grid.size();i++){\n            for(int j=0;j<grid[0].size();j++){\n                if(grid[i][j] == 1 && vis[i][j] == 0){\n                    dp[val] = dfs(grid,i,j,val);\n                    val++;\n                }\n            }  \n        }\n        int ans = 0;\n        for(int i=0;i<grid.size();i++){\n            for(int j=0;j<grid[0].size();j++){\n                if(grid[i][j] == 0){\n                    int temp = 1;\n                    map<int,int> mp;\n                    if(i-1>=0 && vis[i-1][j]){\n                        temp += dp[vis[i-1][j]];\n                        mp[vis[i-1][j]]++;\n                    }\n                    if(j-1>=0 && vis[i][j-1] && !mp[vis[i][j-1]]){\n                        temp += dp[vis[i][j-1]];\n                        mp[vis[i][j-1]]++;\n                    }\n                    if(i+1<grid.size() && vis[i+1][j] && !mp[vis[i+1][j]]){\n                        temp += dp[vis[i+1][j]];\n                        mp[vis[i+1][j]]++;\n                    }\n                    if(j+1<grid[0].size() && vis[i][j+1] && !mp[vis[i][j+1]]){\n                        temp += dp[vis[i][j+1]];\n                        mp[vis[i][j+1]]++;\n                    }\n                    ans = max(ans,temp);\n                }\n            }  \n        }\n        return ans == 0 ? grid.size()*grid[0].size() : ans;\n    }\n};\n```
[]