🌊 Largest Island Expansion 🏝️ 
🧠 Intuition
First, we identify all islands using BFS and assign them unique island numbers.
Store each island’s size in a map {island_number → size}.
For every
# 🧠 Intuition  
- First, we **identify all islands** using **BFS** and assign them unique island numbers.  
- Store each island’s **size** in a map `{island_number → size}`.  
- For every `0`, we check **neighboring islands** and compute the **largest possible island** if that `0` is changed to `1`.  
- Keep track of the **maximum size** found.  

---

# 🚀 Approach  
1. **Step 1: Label Islands**  
   - Use **BFS** to traverse islands and assign each a unique number.  
   - Store the size of each island.  

2. **Step 2: Evaluate 0s**  
   - For each `0`, check adjacent island numbers.  
   - Sum the sizes of unique adjacent islands to get the **largest possible island**.  

3. **Step 3: Return the Maximum Island Size**  
   - The answer is either the **largest existing island** or the **largest one formed by flipping a `0`**.  

---

# ⏳ Complexity Analysis  
- **Time Complexity:**  
  $$O(n^2)$$ — We traverse the grid twice (once for BFS and once for checking `0`s).  
- **Space Complexity:**  
  $$O(n^2)$$ — To store visited states and island sizes.  

---
![c1ee5054-dd07-4caa-a7df-e21647cfae9e_1709942227.5165014.png](https://assets.leetcode.com/users/images/7e0c0309-70f0-48fd-bba7-6234b39fbe2c_1738299519.5819862.png)


# 🧑‍💻 Code  
```cpp []
class Solution {
public:
    int largestIsland(vector<vector<int>>& grid) {
        int n = grid.size(), res = 0;
        vector<vector<bool>> visited(n, vector<bool>(n, false));
        vector<vector<pair<int, int>>> islandMap(n, vector<pair<int, int>>(n));
        
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                islandMap[i][j] = {grid[i][j], 0};  // (value, island_number)
            }
        }

        int islandNum = 1;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (!visited[i][j] && grid[i][j]) {
                    res = max(res, bfs(islandMap, visited, i, j, islandNum));
                    islandNum++;
                }
            }
        }

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (!grid[i][j]) {
                    unordered_map<int, int> islandSizes;  
                    if (i - 1 >= 0 && islandMap[i - 1][j].first)
                        islandSizes[islandMap[i - 1][j].second] = islandMap[i - 1][j].first;
                    if (i + 1 < n && islandMap[i + 1][j].first)
                        islandSizes[islandMap[i + 1][j].second] = islandMap[i + 1][j].first;
                    if (j - 1 >= 0 && islandMap[i][j - 1].first)
                        islandSizes[islandMap[i][j - 1].second] = islandMap[i][j - 1].first;
                    if (j + 1 < n && islandMap[i][j + 1].first)
                        islandSizes[islandMap[i][j + 1].second] = islandMap[i][j + 1].first;

                    int sum = 1;
                    for (auto it : islandSizes)
                        sum += it.second;

                    res = max(res, sum);
                }
            }
        }
        return res;
    }

private:
    int bfs(vector<vector<pair<int, int>>>& grid, vector<vector<bool>>& visited, int i, int j, int num) {
        queue<pair<int, int>> q;
        vector<pair<int, int>> collect;
        int n = grid.size();
        q.push({i, j});

        while (!q.empty()) {
            auto [r, c] = q.front(); q.pop();
            if (visited[r][c]) continue;
            visited[r][c] = true;
            collect.push_back({r, c});

            vector<pair<int, int>> directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
            for (auto [dr, dc] : directions) {
                int nr = r + dr, nc = c + dc;
                if (nr >= 0 && nr < n && nc >= 0 && nc < n && !visited[nr][nc] && grid[nr][nc].first) {
                    q.push({nr, nc});
                }
            }
        }

        for (auto [r, c] : collect) {
            grid[r][c] = {collect.size(), num};
        }
        return collect.size();
    }
};
```


```python []
class Solution:
    def largestIsland(self, grid):
        n = len(grid)
        island_map = [[(grid[r][c], 0) for c in range(n)] for r in range(n)]
        visited = [[False] * n for _ in range(n)]
        
        def bfs(r, c, num):
            q = deque([(r, c)])
            cells = []
            while q:
                r, c = q.popleft()
                if visited[r][c]: continue
                visited[r][c] = True
                cells.append((r, c))
                for dr, dc in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
                    nr, nc = r + dr, c + dc
                    if 0 <= nr < n and 0 <= nc < n and not visited[nr][nc] and grid[nr][nc]:
                        q.append((nr, nc))
            size = len(cells)
            for r, c in cells:
                island_map[r][c] = (size, num)
            return size

        island_sizes, num, max_island = {}, 1, 0
        for r in range(n):
            for c in range(n):
                if grid[r][c] and not visited[r][c]:
                    island_sizes[num] = bfs(r, c, num)
                    max_island = max(max_island, island_sizes[num])
                    num += 1
        
        for r in range(n):
            for c in range(n):
                if grid[r][c] == 0:
                    neighbors = set()
                    for dr, dc in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
                        nr, nc = r + dr, c + dc
                        if 0 <= nr < n and 0 <= nc < n and island_map[nr][nc][0]:
                            neighbors.add(island_map[nr][nc][1])
                    
                    new_size = 1 + sum(island_sizes[i] for i in neighbors)
                    max_island = max(max_island, new_size)

        return max_island
```

---

## 🔍 Examples  
### Example 1  
**Input:** `[[1,0],[0,1]]`  
**Output:** `3`  

### Example 2  
**Input:** `[[1,1],[1,0]]`  
**Output:** `4`  

---

### **Thank you for reading! 😊 Hope this solution helps. Happy coding! 🚀**

![1HBC0324_COV.jpg](https://assets.leetcode.com/users/images/4c024c0b-1970-46eb-acdf-28f2d7849d45_1738299437.418975.jpeg)
['Array', 'Hash Table', 'Breadth-First Search', 'Queue', 'Matrix', 'Simulation', 'Python', 'C++']