C++ Solution || BFS Approach || Detailed Explanation
IntuitionThe problem involves finding the largest possible island in a grid after flipping at most one 0 to 1. The approach involves:
Identifying distinct islan
# Intuition
The problem involves finding the largest possible island in a grid after flipping at most one `0` to `1`. The approach involves:
1. Identifying distinct islands and assigning them unique IDs.
2. Using a BFS traversal to count the size of each island.
3. Storing island sizes in a hashmap.
4. Checking every `0` in the grid and determining the largest possible island by connecting adjacent islands.


# Approach
1. **Identify Islands**
   - Perform BFS traversal to find all distinct islands and assign them unique IDs.
   - Store each island’s size in a hashmap.
   
2. **Check Each Zero (`0`)**
   - For each `0`, check its adjacent cells and collect unique island IDs.
   - Compute the possible island size if the `0` is flipped to `1`.
   - Update the maximum possible island size.

3. **Return the Maximum Island Size**
   - If no `0` is found, return the size of the largest island.



# Steps
```
1. Identify islands and mark them with unique IDs
   ├── Use BFS to traverse each island
   ├── Store each island’s size in a hashmap
   └── Track the largest island found so far

2. Iterate through the grid to find zeroes
   ├── For each zero, check its adjacent cells
   ├── Collect unique island IDs
   ├── Sum up sizes of adjacent islands
   ├── Add 1 to account for flipping the zero to one
   └── Update the maximum possible island size

3. Return the maximum possible island size found
```



# Complexity
- **Time Complexity:** $$O(n^2)$$
- **Space Complexity:** $$O(n^2)$$

---

# Code
```cpp
class Solution {
public:
    int bfs(vector<vector<int>>& grid, int row, int col, int n, int id, vector<vector<int>>& vis) {
        queue<pair<int, int>> q;
        q.push({row, col});
        vis[row][col] = 1;
        grid[row][col] = id;

        int delrow[] = {-1, 0, 1, 0};
        int delcol[] = {0, 1, 0, -1};
        int cnt = 1;
        
        while (!q.empty()) {
            auto [r, c] = q.front();
            q.pop();
            
            for (int i = 0; i < 4; i++) {
                int nrow = r + delrow[i];
                int ncol = c + delcol[i];
                if (nrow >= 0 && nrow < n && ncol >= 0 && ncol < n && grid[nrow][ncol] == 1 && !vis[nrow][ncol]) {
                    vis[nrow][ncol] = 1;
                    grid[nrow][ncol] = id;
                    q.push({nrow, ncol});
                    cnt++;
                }
            }
        }
        return cnt;
    }
    
    int largestIsland(vector<vector<int>>& grid) {
        int n = grid.size();
        int maxi = 0;
        int id = 2;
        unordered_map<int, int> mp;
        vector<vector<int>> vis(n, vector<int>(n, 0));
        int delrow[] = {-1, 0, 1, 0};
        int delcol[] = {0, 1, 0, -1};
        
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1 && !vis[i][j]) {
                    int cnt = bfs(grid, i, j, n, id, vis);
                    mp[id] = cnt;
                    maxi = max(maxi, cnt);
                    id++;
                }
            }
        }
        
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 0) {
                    unordered_set<int> uniqueIslands;
                    for (int d = 0; d < 4; d++) {
                        int nrow = i + delrow[d];
                        int ncol = j + delcol[d];
                        if (nrow >= 0 && nrow < n && ncol >= 0 && ncol < n && grid[nrow][ncol] > 1) {
                            uniqueIslands.insert(grid[nrow][ncol]);
                        }
                    }
                    
                    int newSize = 1;
                    for (int islandId : uniqueIslands) {
                        newSize += mp[islandId];
                    }
                    maxi = max(maxi, newSize);
                }
            }
        }
        
        return maxi;
    }
};
````
![d3550b79-52c8-4704-846f-c00daecb5632_1737784461.667478.png](https://assets.leetcode.com/users/images/8fcd5f03-34bc-4f43-a611-4f9e97592721_1738313998.8675714.png)


['Array', 'Breadth-First Search', 'Matrix', 'C++']