2 Way Simple Stack+Maping/DfS Detailed explanation
Method 1 Stack+unordered mapIntuitionThe problem requires finding the size of the largest island in an n x n binary grid after flipping at most one 0 to 1. An i
# Method 1 Stack+unordered map 
# Intuition
The problem requires finding the size of the largest island in an `n x n` binary grid after flipping at most one `0` to `1`. An island is defined as a group of `1`s connected 4-directionally (up, down, left, right). The challenge is to determine the optimal `0` to flip to maximize the size of the resulting island.

### Key Observations:
1. **Existing Islands**:
   - The grid may already contain multiple islands of varying sizes.
   - We need to know the size of each island and their positions to calculate the potential size after flipping a `0`.

2. **Flipping a `0`**:
   - Flipping a `0` to `1` can connect neighboring islands into a single larger island.
   - The size of the new island depends on the sizes of the neighboring islands and the `0` being flipped.

3. **Edge Cases**:
   - If the grid contains no `0`s, the largest island is simply the largest existing island.
   - If the grid contains no `1`s, flipping any `0` will create an island of size `1`.

# Approach
The solution involves the following steps:

1. **Label Islands**:
   - Traverse the grid and assign a unique label to each island using a flood-fill approach.
   - Store the size of each island in a map for quick lookup.

2. **Evaluate Flipping Each `0`**:
   - For each `0` in the grid, check its 4-directional neighbors.
   - If a neighbor is part of an island, add the size of that island to the total.
   - Use a set to ensure that the same island is not counted multiple times.

3. **Track Maximum Island Size**:
   - Keep track of the maximum island size obtained after flipping each `0`.

4. **Handle Edge Cases**:
   - If there are no `0`s, return the size of the largest existing island.
   - If there are no `1`s, return `1` (since flipping one `0` will create an island of size `1`).

# Complexity
- **Time Complexity**: \(O(n^2)\), where \(n\) is the size of the grid.
  - We traverse the grid twice: once to label islands and once to evaluate flipping each `0`.
- **Space Complexity**: \(O(n^2)\), for storing labels and island sizes.

```C++ []
class Solution {
public:
    int largestIsland(vector<vector<int>>& grid) {
        if (grid.empty())
            return 0;

        int n = grid.size();
        vector<vector<int>> labels(n,vector<int>(n, 0));
        unordered_map<int, int> islandSizes;
        int label = 1;
        int maxSize = 0;

        int dirs[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                if (grid[i][j] == 1 && labels[i][j] == 0) {
                    int size = 0;
                    vector<pair<int, int>> stack;
                    stack.push_back({i, j});
                    labels[i][j] = label;

                    while (!stack.empty()) {
                        auto [x, y] = stack.back();
                        stack.pop_back();
                        size++;

                        for (auto [dx, dy] : dirs) {
                            int nx = x + dx, ny = y + dy;
                            if (nx >= 0 && nx < n && ny >= 0 && ny < n &&
                                grid[nx][ny] == 1 && labels[nx][ny] == 0) {
                                labels[nx][ny] = label;
                                stack.push_back({nx, ny});
                            }
                        }
                    }

                    islandSizes[label] = size;
                    maxSize = max(maxSize, size);
                    label++;
                }
            }
        }

        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                if (grid[i][j] == 0) {
                    unordered_set<int> neighborLabels;
                    int total = 1;

                    for (auto [dx, dy] : dirs) {
                        int nx = i + dx, ny = j + dy;
                        if (nx >= 0 && nx < n && ny >= 0 && ny < n &&
                            grid[nx][ny] == 1) {
                            neighborLabels.insert(labels[nx][ny]);
                        }
                    }

                    for (int lbl : neighborLabels) {
                        total += islandSizes[lbl];
                    }

                    maxSize = max(maxSize, total);
                }
            }
        }

        return maxSize;
    }
};
```
# 🌟 Intuition
The problem requires us to find the largest island that can be formed by converting at most one water cell (`0`) into a land cell (`1`). The grid consists of `1`s (land) and `0`s (water), and the goal is to maximize the size of the island that can be created after flipping a single `0` to `1`.

### Key Insights:
1. **Island Definition**: An island is a contiguous block of `1`s, connected either horizontally or vertically. Diagonal connections do not count as valid island connections.
2. **DFS Traversal**: To identify the size of each island, we will perform a **Depth First Search (DFS)**. This will allow us to count the number of connected `1`s for each island and store it in a map.
3. **Maximizing the Island Size**: After identifying the islands, we will check each water cell (`0`) to see if changing it to land will merge any adjacent islands. This gives us the potential for a larger island.

---

# 🚀 Approach

### Step 1: **DFS to Identify Island Sizes**
   - **Goal**: Traverse the grid and identify each individual island, counting the size of each island.
   - **DFS Process**: We start from any unvisited land cell (`1`), then explore all its neighboring cells recursively in the four directions (up, down, left, right). Every time we reach a connected land cell, we mark it as visited and count it as part of the current island.
   - **Key Steps**:
     - Traverse the grid cell by cell.
     - If the cell is `1` (land) and unvisited, perform DFS from that cell to explore the entire island.
     - During the DFS, assign each island a unique identifier (key). We use this key to track and store the size of each island in a map (`unordered_map<int, int> unmap`).

### Step 2: **Exploring Water Cells to Form Larger Islands**
   - **Goal**: For each water cell (`0`), check the neighboring cells to see if converting the water cell into land will merge any neighboring islands.
   - **Neighboring Islands**: A water cell can potentially merge multiple neighboring islands. We need to:
     - Check the four neighboring cells (up, down, left, right).
     - Collect the unique island identifiers of the neighboring cells.
     - Sum the sizes of all neighboring islands to calculate the potential size of the new island if the current water cell is turned into land.
     - Track the maximum possible size of the island formed by flipping a water cell to land.

### Step 3: **Edge Case Handling**
   - **All Water Cells**: If the grid is made entirely of water cells, the largest possible island would be the size of the entire grid (`n * n`), as converting any one of the water cells will create a new island.
   - **No Valid Expansion**: If there is no water cell that can combine islands, the largest existing island size will be the result.

---

# 🧮 Complexity

- **Time Complexity**: 
  - The time complexity is primarily determined by the number of cells in the grid. We traverse each cell twice:
    1. **DFS Traversal**: During the DFS, we visit each land cell exactly once. The DFS will take `O(n^2)` time in the worst case, where `n` is the size of the grid.
    2. **Exploring Water Cells**: For each water cell, we check its four neighboring cells and calculate the potential island size by summing neighboring island sizes. This step also takes `O(n^2)` time because we iterate over all water cells.
  - Overall time complexity: $$O(n^2)$$, where `n` is the number of rows (or columns) in the grid.
---
# Code
```cpp []
class Solution {
public:
    unordered_map<int, int> unmap;

    int dfs(int i, int j, vector<vector<int>>& grid, vector<vector<bool>>& visited, int key) {
        int n = grid.size();
        if (i < 0 || j < 0 || i >= n || j >= n || visited[i][j] || grid[i][j] == 0) {
            return 0;
        }
        visited[i][j] = true;
        int count = 1 + dfs(i + 1, j, grid, visited, key)
                    + dfs(i - 1, j, grid, visited, key)
                    + dfs(i, j + 1, grid, visited, key)
                    + dfs(i, j - 1, grid, visited, key);
        grid[i][j] = key;
        return count;
    }

    int largestIsland(vector<vector<int>>& grid) {
        int n = grid.size();
        int key = 2;
        vector<vector<bool>> visited(n, vector<bool>(n, false));

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (!visited[i][j] && grid[i][j] == 1) {
                    int count = dfs(i, j, grid, visited, key);
                    unmap[key] = count;
                    key++;
                }
            }
        }

        int result = -1;
        vector<vector<bool>> visited2(n, vector<bool>(n, false));

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 0) {
                    int a = (i + 1 < n) ? grid[i + 1][j] : 0;
                    int b = (i - 1 >= 0) ? grid[i - 1][j] : 0;
                    int c = (j + 1 < n) ? grid[i][j + 1] : 0;
                    int d = (j - 1 >= 0) ? grid[i][j - 1] : 0;
                    set<int> st;
                    st.insert(a);
                    st.insert(b);
                    st.insert(c);
                    st.insert(d);
                    int res = 1;
                    for (auto it = st.begin(); it != st.end(); it++) {
                        res += unmap[*it];
                    }
                    result = max(result, res);
                }
            }
        }

        if (result == -1) {
            return n * n;
        }
        return result;
    }
};

```
['Depth-First Search', 'Ordered Map', 'Matrix', 'C++']