✅ Making A Large Island | Explanation w/Comments in Code | DFS + BFS
Solution 1(DFS + BFS):\n\n# Algorithm:\nStep 1: Find out all the connected components and assign each component an index.\nStep 2: While calculating the connect
***Solution 1(DFS + BFS):***\n```\n# Algorithm:\nStep 1: Find out all the connected components and assign each component an index.\nStep 2: While calculating the connected components , also calculate the area for that connected component.\nStep 3: Use HashMap to store the mapping between component index and its corresponding area.\nStep 4: Use BFS to find out the max Area by flipping each zero one by one.\n\nNOTE:\n1) Zero can be a part of more than one connected component,\n2) While calculating the area , dont forget to add 1 to the area because the zero is now flipped to 1,\nand we have to consider this value also. \n\nBelow is the step by step code for the above explanation with comments,\n```\n***\n**C++:**\n```\nclass Solution {\n\n// As 0,1 already occupied in matrix so we need to start with index = 2;\nint idx=2;\n\n// HashMap to have mapping between the connected component index and its area\nunordered_map<int,int> mp;\n\n// 4 directions to find out connected 1s\nvector<pair<int,int>> direction{{1,0},{-1,0},{0,1},{0,-1}};\n\n// Globally declaring the area variable which will store the max area\nint area = 0;\n\n// Simple DFS method for assigning connected components an index.\nvoid dfs(int i,int j,vector<vector<int>> &grid)\n{\n    if(i<0 or i>=size(grid) or j<0 or j>=size(grid) or grid[i][j]!=1)\n        return;\n    mp[idx]++;\n    grid[i][j]=idx;\n    for(auto dir:direction)\n    {\n        dfs(i+dir.first,j+dir.second,grid);\n    }\n}\n\n// Method to mark all the connected components.\nvoid markAllTheConnectedComponents(vector<vector<int>>& grid)\n{\n    int n=size(grid);\n    mp.clear();\n    idx=2;\n    for(int i=0;i<n;i++)\n    {\n        for(int j=0;j<n;j++)\n        {\n            if(grid[i][j])\n            {\n                dfs(i,j,grid);\n            // Here we are handling the situation when there is no 0 in the matrix.\n                area=max(area,mp[idx]);\n                idx++;\n            }\n        }\n    }\n}\n\n// Method to find out the max area in case of any 0 to be flipped.\nvoid findMaxArea(vector<vector<int>>& grid)\n{\n    int n=size(grid);\n    queue<pair<int,int>> q;\n    \n//     Push all the {i,j} where grid[i][j]==0 in queue.\n    for(int i=0;i<n;i++)\n    {\n        for(int j=0;j<n;j++)\n        {\n            if(grid[i][j]==0)\n            {\n                q.push({i,j});\n            }\n        }\n    }\n\n    auto isValid = [&](int i,int j){\n        return (i>=0 and i<n and j>=0 and j<n and grid[i][j]!=0);\n    };\n\n    while(!q.empty())\n    {\n        auto front = q.front();\n        q.pop();\n        int i = front.first;\n        int j = front.second;\n        \n        unordered_set<int> vis;\n        int curr = 0;\n        for(auto dir:direction)\n        {\n            int newi = i+dir.first;\n            int newj = j+dir.second;\n            \n            if(isValid(newi,newj) and !vis.count(grid[newi][newj]))\n            {\n                vis.insert(grid[newi][newj]);\n                curr += mp[grid[newi][newj]];\n            }\n        }\n//         its curr+1, why? because we need to consider the flipped 0 also.\n        area = max(curr+1,area);\n    }\n}\n\n\npublic:\n    int largestIsland(vector<vector<int>>& grid) \n    {\n//         Step 1: Mark all the connected componentes with index.\n        markAllTheConnectedComponents(grid);\n//         Step 2: Do BFS to find which 0 flip will result in the larger area.\n        findMaxArea(grid);\n        return area;\n    }\n};\n```\n***\n**If you found the post useful, do consider it for upvotes.\uD83D\uDE0A**\n***
[]