DFS Solution(With Explanation)
If you like the Solution, then please Upvote!\n\n\nRefer This Medium Post for better Understanding: https://medium.com/@amitsingh_51985/making-a-large-island-le
**If you like the Solution, then please Upvote!**\n![image](https://assets.leetcode.com/users/images/5e590ed2-e526-4c5e-83c9-312677e006f7_1647181101.9379933.png)\n\nRefer This Medium Post for better Understanding: https://medium.com/@amitsingh_51985/making-a-large-island-leetcode-36b0d05b3175\n\n**C++**\n\n    class Solution {\n    public:\n    int dfs(int i, int j, vector<vector<int>> &grid, int & color,int rows,int cols)\n    {      \n        if(i < 0 || j < 0 || i >= rows || j >= cols)//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,rows,cols);\n        count += dfs(i - 1, j , grid,color,rows,cols);\n        count += dfs(i, j + 1, grid,color,rows,cols);\n        count += dfs(i, j - 1, grid,color,rows,cols);\n        \n        return count;\n    }\n    \n \n    int largestIsland(vector<vector<int>>& grid) \n    {\n        int rows=grid.size();\n        int cols=grid[0].size();\n        \n        int color = 2;//after visiting any 1, we change that one by color val and then move to its adjacent element, when their is no adjacent increment the color val\n        \n        unordered_map<int,int>mp;\n        \n         for(int i = 0; i < rows; i++)\n         {\n            for(int j = 0; j < cols; j++)\n            {\n                if(grid[i][j] == 1)\n                {\n                    int count = dfs(i, j, grid,color,rows,cols);//insert the value of particular area in map with its 1\'s count\n                        mp[color] = count;\n                        color++;\n                     \n                }\n            }\n        }\n        //Now we are changing one 0 to 1 and checking for every case and find max island with 1\'s\n        int result=0;\n        for(int i=0;i<rows;i++)\n        {\n            for(int j=0;j<cols;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<rows && 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<cols && 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        return result==0?(rows*cols):result; \n    }\n    };\n\t\n**Java:**\n\n    class Solution {\n    public int dfs(int i, int j, int[][] grid, int rows, int cols, int color) {\n        // Recursive depth-first search (DFS) function to explore the island.\n        if (i < 0 || i >= rows || j < 0 || j >= cols)\n            return 0; // If we\'re out of bounds, return 0.\n        if (grid[i][j] == 0 || grid[i][j] == color)\n            return 0; // If the current cell is water or has already been visited with the same color, return 0.\n\n        grid[i][j] = color; // Mark the cell with the current color.\n        int count = 1; // Initialize the island size count to 1 (for the current cell).\n\n        // Recursively explore neighboring cells in all four directions.\n        count += dfs(i + 1, j, grid, rows, cols, color);\n        count += dfs(i - 1, j, grid, rows, cols, color);\n        count += dfs(i, j - 1, grid, rows, cols, color);\n        count += dfs(i, j + 1, grid, rows, cols, color);\n\n        return count; // Return the total island size.\n    }\n\n    public int largestIsland(int[][] grid) {\n        int rows = grid.length;\n        int cols = grid[0].length;\n\n        HashMap<Integer, Integer> mp = new HashMap<>(); // A HashMap to store island colors and their respective sizes.\n        int color = 2; // Start with the color \'2\' for the first island.\n\n        // Iterate through the grid to identify and label islands with unique colors.\n        for (int i = 0; i < rows; i++) {\n            for (int j = 0; j < cols; j++) {\n                if (grid[i][j] == 1) {\n                    int count = dfs(i, j, grid, rows, cols, color); // Perform DFS to find the size of the island.\n                    mp.put(color, count); // Store the island\'s color and size in the HashMap.\n                    color++; // Move to the next color for the next island.\n                }\n            }\n        }\n\n        int result = 0; // Initialize the result as 0.\n\n        // Iterate through the grid again to find the largest possible island.\n        for (int i = 0; i < rows; i++) {\n            for (int j = 0; j < cols; j++) {\n                if (grid[i][j] == 0) {\n                    HashSet<Integer> st = new HashSet<>(); // HashSet to store unique neighboring island colors.\n\n                    // Check the colors of neighboring cells and add them to the HashSet.\n                    if (i - 1 >= 0 && grid[i - 1][j] != 0)\n                        st.add(grid[i - 1][j]);\n                    if (i + 1 < rows && grid[i + 1][j] != 0)\n                        st.add(grid[i + 1][j]);\n                    if (j - 1 >= 0 && grid[i][j - 1] != 0)\n                        st.add(grid[i][j - 1]);\n                    if (j + 1 < cols && grid[i][j + 1] != 0)\n                        st add(grid[i][j + 1]);\n\n                    int sum = 1; // Initialize the size of the current possible island (1 for the current cell).\n\n                    // Calculate the total size of the possible island by adding sizes of neighboring islands.\n                    for (int it : st)\n                        sum += mp.get(it);\n\n                    result = Math.max(result, sum); // Update the result with the maximum island size found.\n\n                }\n            }\n        }\n\n        // If no land is present in the grid, return the total grid size as the result.\n        return result == 0 ? (rows * cols) : result;\n    }\n    }\n
['Depth-First Search', 'Graph', 'C', 'C++', 'Java']