Easy & Detailed Approch💡 | BFS ✅ | HashMap✅ | All Languages 🔥 
IntuitionThe problem requires us to find the largest possible island in a given grid, where an island is a group of 1s connected vertically or horizontally. We
# Intuition
The problem requires us to find the largest possible island in a given grid, where an island is a group of `1`s connected vertically or horizontally. We can also convert one `0` into a `1` to maximize the island size.

To solve this, we first identify all existing islands, assign them unique IDs, and store their sizes. Then, for each `0`, we check adjacent islands and compute the maximum possible island size after flipping it to `1`.

# Approach
1. **Identify Islands**  
   - Use **BFS** to traverse the grid and find all islands.
   - Assign each island a unique ID starting from `2` (since `0` and `1` are already used).
   - Store the size of each island in a **hashmap** (`maxisland[id]`).

2. **Calculate Maximum Island Size**
   - Iterate through the grid, checking each `0`.
   - Use a **set** to track unique island IDs adjacent to this `0`.
   - Sum up their sizes and compute the potential largest island if we flip this `0` to `1`.

3. **Return the Maximum Island Size**
   - Keep track of the largest island found during the above process.

# Complexity
- **Time Complexity:**  
  - **O(m × n)** for BFS traversal of all islands.
  - **O(m × n)** for checking each `0` and computing the possible island size.
  - Overall, **O(m × n)**.

- **Space Complexity:**  
  - **O(m × n)** for the visited array.
  - **O(m × n)** for storing island sizes in a hashmap.
  - Overall, **O(m × n)**.


# Code
```cpp []
class Solution {
public:
    // Function to perform BFS and mark all connected components of an island
    void bfs(int m, int n, queue<pair<int, int>>& q, vector<vector<int>>& grid, 
             vector<vector<int>>& vis, int& sum, int id, unordered_map<int, int>& maxisland) {
        int row[4] = {-1, 0, 0, +1}; // Directions for moving up, right, left, down
        int col[4] = {0, +1, -1, 0};

        while (!q.empty()) {
            auto val = q.front();
            int r = val.first;
            int c = val.second;
            q.pop();

            // Explore all 4 possible directions
            for (int i = 0; i < 4; i++) {
                int nrow = r + row[i];
                int ncol = c + col[i];

                // Check if the new position is within bounds and is part of the island
                if (nrow >= 0 && nrow < m && ncol >= 0 && ncol < n && 
                    grid[nrow][ncol] == 1 && vis[nrow][ncol] == 0) {
                    q.push({nrow, ncol});
                    vis[nrow][ncol] = 1; // Mark as visited
                    grid[nrow][ncol] = id; // Assign island ID
                    sum++; // Increase island size count
                }
            }
        }
        maxisland[id] = sum; // Store the size of this island
    }

    int largestIsland(vector<vector<int>>& grid) {
        int m = grid.size();
        int n = grid[0].size();
        vector<vector<int>> vis(m, vector<int>(n, 0)); // Visited matrix
        unordered_map<int, int> maxisland; // Stores the size of each island
        int id = 2; // Start island ID from 2 (to distinguish from 0 and 1)
        int maxi = 0; // Stores the maximum island size found

        // Step 1: Identify all islands and store their sizes
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1 && vis[i][j] == 0) {
                    int sum = 1; // Start with size 1 (current cell)
                    queue<pair<int, int>> q;
                    q.push({i, j});
                    vis[i][j] = 1;
                    grid[i][j] = id; // Assign a unique ID to this island
                    bfs(m, n, q, grid, vis, sum, id, maxisland);
                    maxi = max(maxi, sum); // Update the maximum island size found
                    id++; // Increment island ID for next island
                }
            }
        }

        // Step 2: Try flipping each `0` to `1` and calculate the possible island size
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 0) { // Consider only water cells
                    unordered_set<int> mp; // Store unique adjacent island IDs
                    int num = 1; // Start with size 1 (flipping this cell to land)

                    int row[4] = {-1, 0, 0, +1}; // Directions
                    int col[4] = {0, +1, -1, 0};

                    // Check all 4 directions for adjacent islands
                    for (int k = 0; k < 4; k++) {
                        int nrow = i + row[k];
                        int ncol = j + col[k];

                        // If valid land cell and belongs to an island, add to set
                        if (nrow >= 0 && nrow < m && ncol >= 0 && ncol < n && 
                            grid[nrow][ncol] > 1) {
                            mp.insert(grid[nrow][ncol]); // Store the unique island ID
                        }
                    }

                    // Sum up sizes of all unique adjacent islands
                    for (int val : mp) {
                        num += maxisland[val];
                    }

                    maxi = max(maxi, num); // Update maximum island size found
                }
            }
        }

        return maxi; // Return the largest possible island size
    }
};


```
```javascript []
class Solution {
    // Function to perform BFS and mark all connected components of an island
    bfs(m, n, q, grid, vis, sum, id, maxisland) {
        let row = [-1, 0, 0, 1]; // Directions for moving up, right, left, down
        let col = [0, 1, -1, 0];

        while (q.length) {
            let [r, c] = q.shift();

            // Explore all 4 possible directions
            for (let i = 0; i < 4; i++) {
                let nrow = r + row[i];
                let ncol = c + col[i];

                // Check if the new position is within bounds and is part of the island
                if (nrow >= 0 && nrow < m && ncol >= 0 && ncol < n && grid[nrow][ncol] === 1 && vis[nrow][ncol] === 0) {
                    q.push([nrow, ncol]);
                    vis[nrow][ncol] = 1; // Mark as visited
                    grid[nrow][ncol] = id; // Assign island ID
                    sum[0]++; // Increase island size count
                }
            }
        }
        maxisland[id] = sum[0]; // Store the size of this island
    }

    largestIsland(grid) {
        let m = grid.length;
        let n = grid[0].length;
        let vis = Array.from({ length: m }, () => Array(n).fill(0)); // Visited matrix
        let maxisland = {}; // Stores the size of each island
        let id = 2; // Start island ID from 2 (to distinguish from 0 and 1)
        let maxi = 0; // Stores the maximum island size found

        // Step 1: Identify all islands and store their sizes
        for (let i = 0; i < m; i++) {
            for (let j = 0; j < n; j++) {
                if (grid[i][j] === 1 && vis[i][j] === 0) {
                    let sum = [1]; // Start with size 1 (current cell)
                    let q = [[i, j]];
                    vis[i][j] = 1;
                    grid[i][j] = id; // Assign a unique ID to this island
                    this.bfs(m, n, q, grid, vis, sum, id, maxisland);
                    maxi = Math.max(maxi, sum[0]); // Update the maximum island size found
                    id++; // Increment island ID for next island
                }
            }
        }

        // Step 2: Try flipping each `0` to `1` and calculate the possible island size
        for (let i = 0; i < m; i++) {
            for (let j = 0; j < n; j++) {
                if (grid[i][j] === 0) { // Consider only water cells
                    let mp = new Set(); // Store unique adjacent island IDs
                    let num = 1; // Start with size 1 (flipping this cell to land)

                    let row = [-1, 0, 0, 1]; // Directions
                    let col = [0, 1, -1, 0];

                    // Check all 4 directions for adjacent islands
                    for (let k = 0; k < 4; k++) {
                        let nrow = i + row[k];
                        let ncol = j + col[k];

                        // If valid land cell and belongs to an island, add to set
                        if (nrow >= 0 && nrow < m && ncol >= 0 && ncol < n && grid[nrow][ncol] > 1) {
                            mp.add(grid[nrow][ncol]); // Store the unique island ID
                        }
                    }

                    // Sum up sizes of all unique adjacent islands
                    for (let val of mp) {
                        num += maxisland[val];
                    }

                    maxi = Math.max(maxi, num); // Update maximum island size found
                }
            }
        }

        return maxi; // Return the largest possible island size
    }
}



```
```python []
from collections import deque

class Solution:
    # Function to perform BFS and mark all connected components of an island
    def bfs(self, m, n, q, grid, vis, sum, id, maxisland):
        row = [-1, 0, 0, 1] # Directions for moving up, right, left, down
        col = [0, 1, -1, 0]

        while q:
            r, c = q.popleft()

            # Explore all 4 possible directions
            for i in range(4):
                nrow = r + row[i]
                ncol = c + col[i]

                # Check if the new position is within bounds and is part of the island
                if 0 <= nrow < m and 0 <= ncol < n and grid[nrow][ncol] == 1 and vis[nrow][ncol] == 0:
                    q.append((nrow, ncol))
                    vis[nrow][ncol] = 1 # Mark as visited
                    grid[nrow][ncol] = id # Assign island ID
                    sum[0] += 1 # Increase island size count
        maxisland[id] = sum[0] # Store the size of this island

    def largestIsland(self, grid):
        m = len(grid)
        n = len(grid[0])
        vis = [[0] * n for _ in range(m)] # Visited matrix
        maxisland = {} # Stores the size of each island
        id = 2 # Start island ID from 2 (to distinguish from 0 and 1)
        maxi = 0 # Stores the maximum island size found

        # Step 1: Identify all islands and store their sizes
        for i in range(m):
            for j in range(n):
                if grid[i][j] == 1 and vis[i][j] == 0:
                    sum = [1] # Start with size 1 (current cell)
                    q = deque([(i, j)])
                    vis[i][j] = 1
                    grid[i][j] = id # Assign a unique ID to this island
                    self.bfs(m, n, q, grid, vis, sum, id, maxisland)
                    maxi = max(maxi, sum[0]) # Update the maximum island size found
                    id += 1 # Increment island ID for next island

        # Step 2: Try flipping each `0` to `1` and calculate the possible island size
        for i in range(m):
            for j in range(n):
                if grid[i][j] == 0: # Consider only water cells
                    mp = set() # Store unique adjacent island IDs
                    num = 1 # Start with size 1 (flipping this cell to land)

                    row = [-1, 0, 0, 1] # Directions
                    col = [0, 1, -1, 0]

                    # Check all 4 directions for adjacent islands
                    for k in range(4):
                        nrow = i + row[k]
                        ncol = j + col[k]

                        # If valid land cell and belongs to an island, add to set
                        if 0 <= nrow < m and 0 <= ncol < n and grid[nrow][ncol] > 1:
                            mp.add(grid[nrow][ncol]) # Store the unique island ID

                    # Sum up sizes of all unique adjacent islands
                    for val in mp:
                        num += maxisland[val]

                    maxi = max(maxi, num) # Update maximum island size found

        return maxi # Return the largest possible island size

```
```java []
import java.util.*;

class Solution {
    // Function to perform BFS and mark all connected components of an island
    public void bfs(int m, int n, Queue<int[]> q, int[][] grid, int[][] vis, int[] sum, int id, Map<Integer, Integer> maxisland) {
        int[] row = {-1, 0, 0, 1}; // Directions for moving up, right, left, down
        int[] col = {0, 1, -1, 0};

        while (!q.isEmpty()) {
            int[] val = q.poll();
            int r = val[0];
            int c = val[1];

            // Explore all 4 possible directions
            for (int i = 0; i < 4; i++) {
                int nrow = r + row[i];
                int ncol = c + col[i];

                // Check if the new position is within bounds and is part of the island
                if (nrow >= 0 && nrow < m && ncol >= 0 && ncol < n && grid[nrow][ncol] == 1 && vis[nrow][ncol] == 0) {
                    q.offer(new int[]{nrow, ncol});
                    vis[nrow][ncol] = 1; // Mark as visited
                    grid[nrow][ncol] = id; // Assign island ID
                    sum[0]++; // Increase island size count
                }
            }
        }
        maxisland.put(id, sum[0]); // Store the size of this island
    }

    public int largestIsland(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        int[][] vis = new int[m][n]; // Visited matrix
        Map<Integer, Integer> maxisland = new HashMap<>(); // Stores the size of each island
        int id = 2; // Start island ID from 2 (to distinguish from 0 and 1)
        int maxi = 0; // Stores the maximum island size found

        // Step 1: Identify all islands and store their sizes
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1 && vis[i][j] == 0) {
                    int[] sum = {1}; // Start with size 1 (current cell)
                    Queue<int[]> q = new LinkedList<>();
                    q.offer(new int[]{i, j});
                    vis[i][j] = 1;
                    grid[i][j] = id; // Assign a unique ID to this island
                    bfs(m, n, q, grid, vis, sum, id, maxisland);
                    maxi = Math.max(maxi, sum[0]); // Update the maximum island size found
                    id++; // Increment island ID for next island
                }
            }
        }

        // Step 2: Try flipping each `0` to `1` and calculate the possible island size
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 0) { // Consider only water cells
                    Set<Integer> mp = new HashSet<>(); // Store unique adjacent island IDs
                    int num = 1; // Start with size 1 (flipping this cell to land)

                    int[] row = {-1, 0, 0, 1}; // Directions
                    int[] col = {0, 1, -1, 0};

                    // Check all 4 directions for adjacent islands
                    for (int k = 0; k < 4; k++) {
                        int nrow = i + row[k];
                        int ncol = j + col[k];

                        // If valid land cell and belongs to an island, add to set
                        if (nrow >= 0 && nrow < m && ncol >= 0 && ncol < n && grid[nrow][ncol] > 1) {
                            mp.add(grid[nrow][ncol]); // Store the unique island ID
                        }
                    }

                    // Sum up sizes of all unique adjacent islands
                    for (int val : mp) {
                        num += maxisland.get(val);
                    }

                    maxi = Math.max(maxi, num); // Update maximum island size found
                }
            }
        }

        return maxi; // Return the largest possible island size
    }
}

```

['Array', 'Hash Table', 'Depth-First Search', 'Breadth-First Search', 'Union Find', 'Queue', 'Matrix', 'C++', 'Java', 'Python3']