Making A Large Island [C++]
IntuitionThe problem requires us to find the largest island possible by converting at most one 0 into 1. This means we need to:
Identify all the islands and cal
## Intuition
The problem requires us to find the largest island possible by converting at most one `0` into `1`. This means we need to:
1. Identify all the islands and calculate their sizes.
2. Find all `0` cells and determine how many distinct islands they can connect.
3. Keep track of the maximum possible island size.

## Approach
1. **Label Islands with DFS:**  
   - Traverse the grid and assign unique island IDs starting from `2` (to differentiate from `1`).
   - Store the sizes of each island in a hashmap `{island_id → size}`.
   - Keep track of the largest island seen so far.

2. **Expand a `0` to a `1`:**  
   - For each `0` in the grid, check its four adjacent cells.
   - Use a `set` to collect the unique island IDs of its neighbors.
   - Compute the potential new island size by summing up the sizes of connected islands.

3. **Return the Maximum Size:**  
   - If the grid consists only of `1`s, return `n * n` (already the largest island).
   - Otherwise, return the largest island size found.

## Complexity
- **Time Complexity:**  
  - DFS runs in **\(O(n^2)\)** to mark islands.
  - Checking all `0`s and merging islands takes at most **\(O(n^2)\)**.
  - Overall complexity: **\(O(n^2)\)**.

- **Space Complexity:**  
  - `area` hashmap stores island sizes, which takes **\(O(n^2)\)** in the worst case.
  - Recursion stack depth in DFS is at most **\(O(n^2)\)**.
  - Extra space for `seen` set per `0` cell is **\(O(1)\)**.
  - Overall space complexity: **\(O(n^2)\)**.

## Code
```cpp

class Solution {
public:
    int largestIsland(vector<vector<int>>& grid) {
        int n = grid.size();
        int id = 2;
        unordered_map<int, int> area;
        int max_area = 0;
        
        vector<int> directions = {-1, 0, 1, 0, -1};

        function<int(int, int, int)> dfs = [&](int r, int c, int island_id) {
            if (r < 0 || r >= n || c < 0 || c >= n || grid[r][c] != 1) return 0;
            grid[r][c] = island_id;
            int size = 1;
            for (int d = 0; d < 4; ++d) {
                size += dfs(r + directions[d], c + directions[d + 1], island_id);
            }
            return size;
        };

        for (int r = 0; r < n; ++r) {
            for (int c = 0; c < n; ++c) {
                if (grid[r][c] == 1) {
                    area[id] = dfs(r, c, id);
                    max_area = max(max_area, area[id]);
                    id++;
                }
            }
        }

        for (int r = 0; r < n; ++r) {
            for (int c = 0; c < n; ++c) {
                if (grid[r][c] == 0) {
                    unordered_set<int> seen;
                    int new_area = 1;
                    for (int d = 0; d < 4; ++d) {
                        int nr = r + directions[d], nc = c + directions[d + 1];
                        if (nr >= 0 && nr < n && nc >= 0 && nc < n && grid[nr][nc] > 1) {
                            int island_id = grid[nr][nc];
                            if (!seen.count(island_id)) {
                                new_area += area[island_id];
                                seen.insert(island_id);
                            }
                        }
                    }
                    max_area = max(max_area, new_area);
                }
            }
        }

        return max_area;
    }
};
```
['C++']