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 1s.

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

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;
    }
};