🔥AASAN HAI🔥 || ✅Simple DFS-> With Detailed Explaination✅ || C++
\n\n\n\n# Intuition\n Describe your first thoughts on how to solve this problem. \n1. My first thought was to apply dfs when we encounter 0, and count all the p
![Chinmay Kulkarni.png](https://assets.leetcode.com/users/images/bf45b898-e0e9-499b-bce1-ea6a605c550c_1697476010.472474.png)\n\n![5e590ed2-e526-4c5e-83c9-312677e006f7_1647181101.9379933.png](https://assets.leetcode.com/users/images/3bc9b720-d223-4de8-b1ad-f91004bdb7ad_1697476055.904632.png)\n\n# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n1. My first thought was to apply dfs when we encounter 0, and count all the possibilites of it.\n2. Definitely it will give TLE sso has to think about another one.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n1. We will assign different colors to different islands.\n2. We will be storing color:count in unordered_map.\n3. Do count++ for different color for different island.\n3. Now when we have stored we will iterate through grid and when we encounter 0 we will store all its colors adjacnet in SET.\n4. And at last add all the count which are related in map.\n\n# Complexity\n- Time complexity:\n1. The dfs function has a time complexity of O(N * M), where N is the number of rows and M is the number of columns in the grid. This is because in the worst case, we may visit every cell in the grid once.\n2. The first nested loop in largestIsland iterates over all cells in the grid, resulting in O(N * M) iterations.\n3. The second nested loop in largestIsland iterates over a constant number of cells for each cell visited in the first loop. It performs operations such as set insertions and iterations over sets, which are constant-time operations.\nTherefore, the overall time complexity is O(N * M).\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: O(N * M)\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n\n```\n//Memmory Time Exceded\n\nint dfs(int i, int j, vector<vector<int>>& grid) {\n    int n = grid.size();\n    int m = grid[0].size();\n\n    if (i < 0 || j < 0 || i >= n || j >= m || grid[i][j] != 1) {\n        return 0;\n    }\n\n    grid[i][j] = -1; // Mark cell as visited\n\n    int count = 1; // Count for the current cell\n    count += dfs(i + 1, j, grid); // Visit down\n    count += dfs(i - 1, j, grid); // Visit up\n    count += dfs(i, j + 1, grid); // Visit right\n    count += dfs(i, j - 1, grid); // Visit left\n\n    return count;\n}\n\nint largestIsland(vector<vector<int>>& grid) {\n    int n = grid.size();\n    int m = grid[0].size();\n    int maxIsland = 0;\n\n    for (int i = 0; i < n; i++) {\n        for (int j = 0; j < m; j++) {\n            if (grid[i][j] == 0) {\n                vector<vector<int>> copyGrid = grid; // Create a copy to avoid modifying the original grid\n                copyGrid[i][j] = 1; // Change the current 0 to 1 (simulate changing a 0 to 1)\n                maxIsland = max(maxIsland, dfs(i, j, copyGrid));\n            }\n        }\n    }\n\n    if(maxIsland==0)\n    {\n        return n*m;\n    }\n    else{\n        return maxIsland;\n    } // If there are no zeros, the largest island is 1\n}\n```\n```\nclass Solution {\npublic:\n    int dfs(int i, int j, vector<vector<int>>& grid,int &color) {\n    int n = grid.size();\n    int m = grid[0].size();\n\n    if(i < 0 || j < 0 || i >= n || j >= m)//invalid case\n         return 0;\n    \n    if(grid[i][j] == 0 || grid[i][j] ==  color)//invalid case\n         return 0;\n    \n    grid[i][j] = color;//just assign the value of color to all adjacent 1\'s of grid and increment the count everytime\n    \n    int count = 1;\n    count += dfs(i + 1, j, grid,color);\n    count += dfs(i - 1, j , grid,color);\n    count += dfs(i, j + 1, grid,color);\n    count += dfs(i, j - 1, grid,color);\n    \n    return count;\n}\n\nint largestIsland(vector<vector<int>>& grid) {\n    int n = grid.size();\n    int m = grid[0].size();\n    unordered_map<int,int>mp;\n\n    int color=2;\n\n    for(int i = 0; i < n; i++)\n     {\n        for(int j = 0; j < m; j++)\n        {\n            if(grid[i][j] == 1)\n            {\n                int count = dfs(i, j, grid,color);//insert the value of particular area in map with its 1\'s count\n                    mp[color] = count;\n                    color++;\n                 \n            }\n        }\n    }\n    int result=0;\n    for(int i=0;i<n;i++)\n    {\n        for(int j=0;j<m;j++)\n        {\n            if(grid[i][j]==0)\n            {\n                set<int> st;//here i use set because we want to store connected values of different color counts,checking all the adjacent values\n                \n                if(i-1>=0 && grid[i-1][j]!=0)\n                {\n                    st.insert(grid[i-1][j]);\n                }\n                if(i+1<n && grid[i+1][j]!=0) \n                {\n                    st.insert(grid[i+1][j]);\n                }\n                if(j-1>=0 && grid[i][j-1]!=0) \n                {\n                    st.insert(grid[i][j-1]);\n                }\n                if(j+1<m && grid[i][j+1]!=0) \n                {\n                    st.insert(grid[i][j+1]);\n                }\n                \n                int sum = 1;\n                for(auto i:st)\n                    sum += mp[i];\n                \n                result = max(result, sum);\n                \n            }\n\n        }\n    }\n    if(result==0)\n    {\n        return n*m;\n    }\n    else{\n        return result;\n    }\n\n}\n\n};\n```
['Depth-First Search', 'C++']