DFS+HashMap   (Very easy to understand)
\n### Solution Overview\nThe solution involves two main steps:\n1. Identify and measure each initial island\'s area using DFS, labeling each island with a uniqu
\n### Solution Overview\nThe solution involves two main steps:\n1. **Identify and measure each initial island\'s area** using DFS, labeling each island with a unique identifier. Store each island\'s area in a map with the island\u2019s ID as the key.\n2. **Simulate flipping each `0` cell to `1`** by calculating the total area of neighboring islands and finding the maximum possible island size after a flip.\n\n### Detailed Steps\n1. **Initialize and Label Islands with DFS**\n   - Iterate through each cell in the matrix. If the cell contains `1`, it belongs to an island. Perform a DFS starting from this cell to mark all cells in this island with a unique ID.\n   - During DFS, calculate the area (number of `1`s) in this island and store it in a map, `map`, where the key is the unique ID and the value is the area.\n   - Track the maximum island size from these initial islands to handle cases where no `0` cells are present.\n\n2. **Calculate the Maximum Island Size After a Flip**\n   - Iterate through each cell again. For each `0` cell, consider it as a candidate for flipping.\n   - Use a `Set` to collect the unique IDs of the neighboring islands around the `0` cell to avoid counting the same island multiple times.\n   - Sum the areas of these neighboring islands to get the potential island area if this `0` is flipped. Add `1` to this area (the `0` cell itself) to get the total possible area.\n   - Update the result with the maximum area found across all `0` cells.\n\n3. **Return the Result**\n   - If all cells were initially `1`s, the maximum area will be the product of the matrix size `n * n`.\n   - Otherwise, return the maximum possible island size calculated from flipping one `0`.\n\n### Code Implementation\nHere\'s the code implementing the above solution:\n\n```java\nclass Solution {\n    int n;  // matrix size\n    Map<Integer, Integer> map = new HashMap<>();  // map to store island ID and corresponding area\n    int[][] dirs = new int[][]{{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; // directions for 4-connectivity\n\n    public int largestIsland(int[][] grid) {\n        n = grid.length;\n        int id = 2;  // start island IDs from 2 (1 is already used in grid)\n        int res = 0; // result for the maximum island size\n\n        // Step 1: Find all initial islands and calculate their areas\n        for (int i = 0; i < n; i++) {\n            for (int j = 0; j < n; j++) {\n                if (grid[i][j] == 1) {  // identify an island starting point\n                    int area = dfs(grid, i, j, id);  // calculate the area using DFS\n                    map.put(id, area);               // store area in the map\n                    res = Math.max(res, area);       // update max island size\n                    id++;                            // move to next island ID\n                }\n            }\n        }\n\n        // Step 2: Try flipping each 0 to 1 and calculate the largest possible island\n        for (int i = 0; i < n; i++) {\n            for (int j = 0; j < n; j++) {\n                if (grid[i][j] == 0) {  // candidate cell to flip\n                    Set<Integer> set = new HashSet<>();  // set to store unique neighboring island IDs\n                    int area = 1;  // area starts from 1 for the flipped cell\n\n                    // Check all 4 directions for neighboring islands\n                    for (int[] d : dirs) {\n                        int nextX = i + d[0];\n                        int nextY = j + d[1];\n\n                        // Check boundary and valid island IDs\n                        if (nextX >= 0 && nextX < n && nextY >= 0 && nextY < n) {\n                            int curId = grid[nextX][nextY];\n                            if (curId >= 2 && !set.contains(curId)) {  // ensure unique ID\n                                area += map.get(curId);  // add neighboring island area\n                                set.add(curId);          // record the island ID\n                            }\n                        }\n                    }\n                    res = Math.max(res, area);  // update maximum area found\n                }\n            }\n        }\n\n        return res;  // return the largest possible island size\n    }\n\n    // DFS method to calculate the area of an island and mark its cells with an ID\n    private int dfs(int[][] grid, int i, int j, int id) {\n        if (i < 0 || i >= n || j < 0 || j >= n || grid[i][j] != 1) {\n            return 0;\n        }\n\n        grid[i][j] = id;  // mark the cell with the island ID\n        int area = 1;     // count the current cell\n\n        // Perform DFS in 4 directions\n        for (int[] d : dirs) {\n            int nextX = i + d[0];\n            int nextY = j + d[1];\n            area += dfs(grid, nextX, nextY, id);  // recursive DFS call to adjacent cells\n        }\n\n        return area;\n    }\n}\n```\n\n### Time Complexity Analysis\n1. **DFS Pass for Initial Island Identification**:\n   - Each cell is visited once during DFS traversal to identify all initial islands.\n   - Complexity: \\(O(n^2)\\).\n\n2. **Checking Each Cell for Possible Flip**:\n   - We iterate through each cell again and, for each `0`, check its four neighbors.\n   - Complexity: \\(O(n^2)\\), as each cell has a fixed number of neighbors (4).\n\n3. **Overall Complexity**:\n   - The combined complexity is \\(O(n^2)\\) + \\(O(n^2)\\) = \\(O(n^2)\\).\n\n### Space Complexity Analysis\n- **Auxiliary Data Structures**: We use a `Map` to store each island\'s area, and a `Set` to track neighboring islands around each `0`. These are bounded by the number of cells, so their complexity is \\(O(n^2)\\).\n- **Recursive Stack for DFS**: In the worst case, the DFS stack depth could be \\(O(n^2)\\).\n\n
['Java']