✅ Easy to Understand Approach | DFS | Number of Islands | Detailed Video Explanation🔥
IntuitionThe problem requires finding the largest possible island in a binary n x n grid after converting at most one 0 into 1.
The key observation is that each
# Intuition
The problem requires finding the **largest possible island** in a binary `n x n` grid after converting **at most one** `0` into `1`.  

- The key observation is that each group of connected `1`s forms an **island**.
- By flipping a `0` to `1`, we can **merge** multiple neighboring islands to create a **larger** island.
- To efficiently compute this, we need to **precompute the size of each island** and then determine the **best possible merge** when flipping a `0`.

# Approach
### **Step 1: Color and Store Island Sizes**
- Traverse the grid using **DFS** and assign a **unique color ID** (starting from `2`) to each island.
- Store the **size of each island** in a `HashMap`.

### **Step 2: Evaluate All `0`s for Maximum Island Size**
- For each `0`, check its **neighboring islands** (using 4-directional lookup).
- Sum up the sizes of all **unique** islands connected by flipping this `0`.
- Track the **maximum possible island size**.

### **Step 3: Handle Edge Cases**
- If there are **no `0`s**, return the total size of the grid.
- If there’s only **one island**, return its original size.

# Complexity
- **Time Complexity**:  
  - **DFS Traversal to Color Islands**: \( O(n^2) \)  
  - **Iterating Over `0`s and Checking Neighbors**: \( O(n^2) \)  
  - **Overall Complexity**: **\( O(n^2) \)**  

- **Space Complexity**:  
  - **Grid Modification**: \( O(1) \) (in-place update)  
  - **HashMap to Store Island Sizes**: \( O(n^2) \) (in the worst case)  
  - **Overall Complexity**: **\( O(n^2) \) in the worst case**  


# Code
```java []

class Solution {
    private int n;
    private int[][] grid;
    private Map<Integer, Integer> islandSizes = new HashMap<>();
    private static final int[][] DIRECTIONS = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};

    public int largestIsland(int[][] grid) {
        this.n = grid.length;
        this.grid = grid;
        int color = 2; // Start coloring islands from 2
        int maxIsland = 0;
        boolean hasZero = false;

        // Step 1: Identify and color each island while storing their sizes
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1) {
                    int size = dfs(i, j, color);
                    islandSizes.put(color, size);
                    maxIsland = Math.max(maxIsland, size);
                    color++;
                } else {
                    hasZero = true;
                }
            }
        }

        // If the grid has no zero, return the size of the entire grid
        if (!hasZero) return maxIsland;

        // Step 2: Try converting each 0 into a 1 and compute the largest possible island
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 0) {
                    Set<Integer> visitedIslands = new HashSet<>();
                    int newSize = 1; // Start with 1 (since we are flipping a zero)
                    
                    // Check all 4 directions for adjacent islands
                    for (int[] dir : DIRECTIONS) {
                        int x = i + dir[0], y = j + dir[1];
                        if (isValid(x, y) && grid[x][y] > 1 && visitedIslands.add(grid[x][y])) {
                            newSize += islandSizes.get(grid[x][y]);
                        }
                    }
                    
                    maxIsland = Math.max(maxIsland, newSize);
                }
            }
        }
        
        return maxIsland;
    }

    private int dfs(int i, int j, int color) {
        if (!isValid(i, j) || grid[i][j] != 1) return 0;
        
        grid[i][j] = color; // Mark cell with new color
        int size = 1;
        
        for (int[] dir : DIRECTIONS) {
            size += dfs(i + dir[0], j + dir[1], color);
        }
        
        return size;
    }

    private boolean isValid(int i, int j) {
        return i >= 0 && i < n && j >= 0 && j < n;
    }
}

```


https://youtu.be/RFsWdH5Z1ws


['Array', 'Depth-First Search', 'Matrix', 'Java']