Simple Read Through Intuition - Spicy 🌶️
\n# Code\njava []\n//DFS\n\nimport java.util.*;\n\nclass Solution {\n    private int islandId = 2;\n    private Map<Integer, Integer> islandAreas = new HashMap<
\n# Code\n```java []\n//DFS\n\nimport java.util.*;\n\nclass Solution {\n    private int islandId = 2;\n    private Map<Integer, Integer> islandAreas = new HashMap<>();\n    private int[] rowP = {-1, 0, 0, 1}; // up, left, right, down\n    private int[] colP = {0, -1, 1, 0};\n\n    public int largestIsland(int[][] grid) {\n        int n = grid.length;\n\n        // Label all islands and compute their areas using DFS\n        for (int i = 0; i < n; i++) {\n            for (int j = 0; j < grid[i].length; j++) {\n                if (grid[i][j] == 1) {\n                    int islandArea = dfs(grid, i, j);\n                    islandAreas.put(islandId, islandArea);\n                    islandId++;\n                }\n            }\n        }\n\n        int maxArea = 0;\n        // Check each cell to find the maximum area of an island formed by changing that cell from 0 to 1\n        for (int i = 0; i < n; i++) {\n            for (int j = 0; j < grid[i].length; j++) {\n                if (grid[i][j] == 0) {\n                    int area = 1; // Start with the current cell\n                    Set<Integer> surrounding = new HashSet<>();\n                    for (int d = 0; d < rowP.length; d++) {\n                        int newI = i + rowP[d], newJ = j + colP[d];\n                        if (newI >= 0 && newI < n && newJ >= 0 && newJ < grid[0].length && grid[newI][newJ] != 0) {\n                            surrounding.add(grid[newI][newJ]);\n                        }\n                    }\n                    for (int id : surrounding) {\n                        area += islandAreas.getOrDefault(id, 0);\n                    }\n                    maxArea = Math.max(maxArea, area);\n                }\n            }\n        }\n\n        return maxArea > 0 ? maxArea : n * n;\n    }\n\n    private int dfs(int[][] grid, int i, int j) {\n        if (i < 0 || i >= grid.length || j < 0 || j >= grid[i].length || grid[i][j] != 1) {\n            return 0;\n        }\n        grid[i][j] = islandId;\n        int area = 1;\n        for (int d = 0; d < rowP.length; d++) {\n            area += dfs(grid, i + rowP[d], j + colP[d]);\n        }\n        return area;\n    }\n}\n\n// Time Complexity: O(N^2)\n// Space Complexity: O(N^2)\n\n\n```\n``` java []\nclass Solution {\n    private int islandId = 2;\n    private Map<Integer, Integer> islandAreas = new HashMap<>();\n    private int[] rowP = {-1, 0, 0, 1}; // up, left, right, down\n    private int[] colP = {0, -1, 1, 0};\n\n    public int largestIsland(int[][] grid) {\n        int n = grid.length;\n\n        // Label all islands and compute their areas using BFS\n        for (int i = 0; i < n; i++) {\n            for (int j = 0; j < grid[i].length; j++) {\n                if (grid[i][j] == 1) {\n                    int islandArea = bfs(grid, i, j);\n                    islandAreas.put(islandId, islandArea);\n                    islandId++;\n                }\n            }\n        }\n\n        int maxArea = 0;\n        // Check each cell to find the maximum area of an island formed by changing that cell from 0 to 1\n        for (int i = 0; i < n; i++) {\n            for (int j = 0; j < grid[i].length; j++) {\n                if (grid[i][j] == 0) {\n                    int area = 1; // Start with the current cell\n                    Set<Integer> surrounding = new HashSet<>();\n                    for (int d = 0; d < rowP.length; d++) {\n                        int newI = i + rowP[d], newJ = j + colP[d];\n                        if (newI >= 0 && newI < n && newJ >= 0 && newJ < grid[0].length && grid[newI][newJ] != 0) {\n                            surrounding.add(grid[newI][newJ]);// note BFS can be done in set and Set reference TUF by Striver\n                        }\n                    }\n                    for (int id : surrounding) {\n                        area += islandAreas.getOrDefault(id, 0);\n                    }\n                    maxArea = Math.max(maxArea, area);\n                }\n            }\n        }\n\n        return maxArea > 0 ? maxArea : n * n;\n    }\n\n    private int bfs(int[][] grid, int i, int j) {\n        Queue<int[]> queue = new LinkedList<>();\n        queue.add(new int[]{i, j});\n        grid[i][j] = islandId;\n        int area = 0;\n\n        while (!queue.isEmpty()) {\n            int[] current = queue.poll();\n            int x = current[0], y = current[1];\n            area++;\n\n            for (int d = 0; d < rowP.length; d++) {\n                int newX = x + rowP[d], newY = y + colP[d];\n                if (newX >= 0 && newX < grid.length && newY >= 0 && newY < grid[0].length && grid[newX][newY] == 1) {\n                    grid[newX][newY] = islandId;\n                    queue.add(new int[]{newX, newY});\n                }\n            }\n        }\n\n        return area;\n    }\n}\n\n\n// Time Complexity: O(N^2)\n// Space Complexity: O(N^2)\n\n\n/*\nIn the context of finding the largest island by converting a 0 to 1, the use of a Set to track unique island IDs rather than a conventional queue is a design choice related to the specific needs of the problem. Let\'s clarify why a Set is used and not a queue in this particular situation:\n\nWhy Use a Set Instead of a Queue\nPurpose of the Set:\n\nUnique Tracking: The Set (specifically, a HashSet in Java) is used to keep track of the unique island IDs that are adjacent to a 0 cell being considered for conversion. The goal here is to ensure that each island\'s area is only counted once when merging.\nPrevent Duplicate Counting: Using a Set avoids counting the area of the same island multiple times. If multiple adjacent 0 cells could potentially connect to the same island, the Set ensures that each island ID is processed only once.\nRole of the Queue in BFS:\n\nBFS Exploration: In the BFS approach, a Queue is essential for exploring the grid level by level. It maintains the order of nodes to visit next and is crucial for traversing the island nodes iteratively.\nNot Needed for Tracking Unique IDs: The Queue is not used to track unique IDs; instead, it is used for the traversal process itself. Once an island is identified, its ID and area are recorded, and the queue is not needed for the subsequent task of calculating potential merged areas.\nConventional Queue and Its Use\nThe conventional Queue is used for the BFS traversal to explore the grid systematically. For BFS, you need to keep track of the cells to be explored next. However, in the step where you calculate the maximum island area possible by converting a 0, the queue\u2019s role is no longer relevant. At this stage, you are simply aggregating the areas of unique islands, not traversing the grid.\n\nSummary\nSet for Tracking Unique Island IDs: Used to collect and avoid duplicate processing of island IDs adjacent to a 0.\nQueue for BFS Traversal: Used to explore nodes level by level during the BFS traversal.\n\n\n*/\n```\n\n```java []\n\n//BFS\n\nclass Solution {\n    private int islandId = 2;\n    private Map<Integer, Integer> islandAreas = new HashMap<>();\n    private int[] rowP = {-1, 0, 0, 1}; // up, left, right, down\n    private int[] colP = {0, -1, 1, 0};\n\n    public int largestIsland(int[][] grid) {\n        int n = grid.length;\n\n        // Label all islands and compute their areas using BFS\n        for (int i = 0; i < n; i++) {\n            for (int j = 0; j < grid[i].length; j++) {\n                if (grid[i][j] == 1) {\n                    int islandArea = bfs(grid, i, j);\n                    islandAreas.put(islandId, islandArea);\n                    islandId++;\n                }\n            }\n        }\n\n        int maxArea = 0;\n        // Check each cell to find the maximum area of an island formed by changing that cell from 0 to 1\n        for (int i = 0; i < n; i++) {\n            for (int j = 0; j < grid[i].length; j++) {\n                if (grid[i][j] == 0) {\n                    int area = 1; // Start with the current cell\n                    Set<Integer> surrounding = new HashSet<>();\n                    for (int d = 0; d < rowP.length; d++) {\n                        int newI = i + rowP[d], newJ = j + colP[d];\n                        if (newI >= 0 && newI < n && newJ >= 0 && newJ < grid[0].length && grid[newI][newJ] != 0) {\n                            surrounding.add(grid[newI][newJ]);// note BFS can be done in set and Set reference TUF by Striver\n                        }\n                    }\n                    for (int id : surrounding) {\n                        area += islandAreas.getOrDefault(id, 0);\n                    }\n                    maxArea = Math.max(maxArea, area);\n                }\n            }\n        }\n\n        return maxArea > 0 ? maxArea : n * n;\n    }\n\n    private int bfs(int[][] grid, int i, int j) {\n        Queue<int[]> queue = new LinkedList<>();\n        queue.add(new int[]{i, j});\n        grid[i][j] = islandId;\n        int area = 0;\n\n        while (!queue.isEmpty()) {\n            int[] current = queue.poll();\n            int x = current[0], y = current[1];\n            area++;\n\n            for (int d = 0; d < rowP.length; d++) {\n                int newX = x + rowP[d], newY = y + colP[d];\n                if (newX >= 0 && newX < grid.length && newY >= 0 && newY < grid[0].length && grid[newX][newY] == 1) {\n                    grid[newX][newY] = islandId;\n                    queue.add(new int[]{newX, newY});\n                }\n            }\n        }\n\n        return area;\n    }\n}\n\n\n// Time Complexity: O(N^2)\n// Space Complexity: O(N^2)\n```
['Array', 'Depth-First Search', 'Breadth-First Search', 'Matrix', 'Java']