> For the complete documentation index, see [llms.txt](https://soumyajit4419.gitbook.io/ds-algo/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://soumyajit4419.gitbook.io/ds-algo/graph/36.-making-a-large-island.md).

# 36. Making A Large Island

You are given an `n x n` binary matrix `grid`. You are allowed to change **at most one** `0` to be `1`.

Return *the size of the largest **island** in* `grid` *after applying this operation*.

An **island** is a 4-directionally connected group of `1`s.

**Example 1:**

```
Input: grid = [[1,0],[0,1]]
Output: 3
Explanation: Change one 0 to 1 and connect two 1s, then we get an island with area = 3.
```

**Example 2:**

```
Input: grid = [[1,1],[1,0]]
Output: 4
Explanation: Change the 0 to 1 and make the island bigger, only one island with area = 4.
```

**Example 3:**

```
Input: grid = [[1,1],[1,1]]
Output: 4
Explanation: Can't change any 0 to 1, only one island with area = 4.
```

## Solution: 

Changing every 0 to 1 and checking the largest island that can be formed

## Solution:(Optimized)

**Approach: Finding already present component size and then changing o -> 1 to find the largest possible**

```cpp
class Solution
{
public:
    unordered_map<int, int> component;

    void dfs(vector<vector<int>> &grid, int x, int y, int color)
    {
        int n = grid.size();
        int m = grid[0].size();

        component[color]++;
        grid[x][y] = color;

        if (x - 1 >= 0 && grid[x - 1][y] == 1)
        {
            dfs(grid, x - 1, y, color);
        }

        if (x + 1 < n && grid[x + 1][y] == 1)
        {
            dfs(grid, x + 1, y, color);
        }

        if (y - 1 >= 0 && grid[x][y - 1] == 1)
        {
            dfs(grid, x, y - 1, color);
        }

        if (y + 1 < m && grid[x][y + 1] == 1)
        {
            dfs(grid, x, y + 1, color);
        }

        return;
    }

    int largestIsland(vector<vector<int>> &grid)
    {

        int n = grid.size();
        int m = grid[0].size();

        int color = 2;

        int ans = 0;
        for (int i = 0; i < grid.size(); i++)
        {
            for (int j = 0; j < grid[0].size(); j++)
            {
                if (grid[i][j] == 1)
                {
                    dfs(grid, i, j, color);
                    ans = max(ans, component[color]);
                    color++;
                }
            }
        }

        for (int i = 0; i < grid.size(); i++)
        {
            for (int j = 0; j < grid[0].size(); j++)
            {

                unordered_set<int> ct;
                if (grid[i][j] == 0)
                {
                    int a = 0, b = 0, c = 0, d = 0;

                    if (i - 1 >= 0 && grid[i - 1][j] != 0)
                    {

                        int col = grid[i - 1][j];

                        if (ct.find(col) == ct.end())
                        {
                            a += component[col];
                            ct.insert(col);
                        }
                    }

                    if (i + 1 < n && grid[i + 1][j] != 0)
                    {
                        int col = grid[i + 1][j];

                        if (ct.find(col) == ct.end())
                        {
                            b += component[col];
                            ct.insert(col);
                        }
                    }

                    if (j - 1 >= 0 && grid[i][j - 1] != 0)
                    {
                        int col = grid[i][j - 1];

                        if (ct.find(col) == ct.end())
                        {
                            c += component[col];
                            ct.insert(col);
                        }
                    }

                    if (j + 1 < m && grid[i][j + 1] != 0)
                    {
                        int col = grid[i][j + 1];

                        if (ct.find(col) == ct.end())
                        {
                            d += component[col];
                            ct.insert(col);
                        }
                    }

                    ans = max(ans, a + b + c + d + 1);
                }
            }
        }

        return ans;
    }
};
```