<p>You are given an <code>n x n</code> binary matrix <code>grid</code>. You are allowed to change <strong>at most one</strong> <code>0</code> to be <code>1</code>.</p>

<p>Return <em>the size of the largest <strong>island</strong> in</em> <code>grid</code> <em>after applying this operation</em>.</p>

<p>An <strong>island</strong> is a 4-directionally connected group of <code>1</code>s.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

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

<p><strong class="example">Example 2:</strong></p>

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

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> grid = [[1,1],[1,1]]
<strong>Output:</strong> 4
<strong>Explanation:</strong> Can&#39;t change any 0 to 1, only one island with area = 4.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>n == grid.length</code></li>
	<li><code>n == grid[i].length</code></li>
	<li><code>1 &lt;= n &lt;= 500</code></li>
	<li><code>grid[i][j]</code> is either <code>0</code> or <code>1</code>.</li>
</ul>

// class DisjointSet {
// public:
//     vector<int> rank, parent, size;

//     DisjointSet(int n) {
//         rank.resize(n + 1, 0);
//         parent.resize(n + 1);
//         size.resize(n + 1);
//         for (int i = 0; i <= n; i++) {
//             parent[i] = i;
//             size[i] = 1;
//         }
//     }

//     int findUPar(int node) {
//         if (node == parent[node])
//             return node;
//         return parent[node] = findUPar(parent[node]);
//     }

//     void unionByRank(int u, int v) {
//         int ulp_u = findUPar(u);
//         int ulp_v = findUPar(v);
//         if (ulp_u == ulp_v)
//             return;
//         if (rank[ulp_u] < rank[ulp_v]) {
//             parent[ulp_u] = ulp_v;
//         } else if (rank[ulp_v] < rank[ulp_u]) {
//             parent[ulp_v] = ulp_u;
//         } else {
//             parent[ulp_v] = ulp_u;
//             rank[ulp_u]++;
//         }
//     }

//     void unionBySize(int u, int v) {
//         int ulp_u = findUPar(u);
//         int ulp_v = findUPar(v);
//         if (ulp_u == ulp_v)
//             return;
//         if (size[ulp_u] < size[ulp_v]) {
//             parent[ulp_u] = ulp_v;
//             size[ulp_v] += size[ulp_u];
//         } else {
//             parent[ulp_v] = ulp_u;
//             size[ulp_u] += size[ulp_v];
//         }
//     }
// };

// class Solution {
// public:
//     bool isvalid(int i, int j, int n) {
//         return i >= 0 && j >= 0 && i < n && j < n;
//     }

//     int largestIsland(vector<vector<int>>& grid) {
//         int n = grid.size();
//         DisjointSet dsu(n * n);

//         for (int i = 0; i < n; i++) {
//             for (int j = 0; j < n; j++) {
//                 if (grid[i][j] == 0) continue;

//                 int dr[] = {-1, 1, 0, 0};
//                 int dc[] = {0, 0, -1, 1};

//                 for (int k = 0; k < 4; k++) {
//                     int newr = i + dr[k];
//                     int newc = j + dc[k];
//                     if (isvalid(newr, newc, n) && grid[newr][newc] == 1) {
//                         int node_no = i * n + j;
//                         int adj_node_no = newr * n + newc;
//                         dsu.unionBySize(node_no, adj_node_no);
//                     }
//                 }
//             }
//         }

//         int mx = 0;
//         for (int i = 0; i < n; i++) {
//             for (int j = 0; j < n; j++) {
//                 if (grid[i][j] == 1) continue;

//                 int dr[] = {-1, 1, 0, 0};
//                 int dc[] = {0, 0, -1, 1};
//                 unordered_set<int> st;

//                 for (int k = 0; k < 4; k++) {
//                     int newr = i + dr[k];
//                     int newc = j + dc[k];
//                     if (isvalid(newr, newc, n) && grid[newr][newc] == 1) {
//                         st.insert(dsu.findUPar(newr * n + newc));
//                     }
//                 }

//                 int total_size = 0;
//                 for (auto it : st) {
//                     total_size += dsu.size[it];
//                 }
//                 mx = max(mx, total_size + 1); // Including the current cell
//                 being converted to 1
//             }
//         }

//         for (int cellNo = 0; cellNo < n * n; cellNo++) {
//             mx = max(mx, dsu.size[dsu.findUPar(cellNo)]);
//         }

//         return mx;
//     }
// };
int assign_id_area(int id, int i, int j, vector<vector<int>>& grid, int n) {
    if (i < 0 || j < 0 || i >= n || j >= n || grid[i][j] != 1) {
        return 0;
    }
    grid[i][j] = id; // change the grid value to their corresponding id
    return 1 + assign_id_area(id, i - 1, j, grid, n) +
           assign_id_area(id, i, j - 1, grid, n) +
           assign_id_area(id, i + 1, j, grid, n) +
           assign_id_area(id, i, j + 1, grid, n);
}

class Solution {
public:
    int largestIsland(vector<vector<int>>& grid) {
        int n = grid.size();
        int id = 2;                 // minimum id is 2 0/1 occupied alreday
        unordered_map<int, int> mp; // map to area;

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1) { // so assign the id with the area
                    int area = assign_id_area(id,i,j,grid, n);
                    mp[id] = area;
                    id++;
                }
            }
        }

        // now we have all all the area marked with their id.
           int ans = 0;
        for (const auto& entry : mp) {
            ans = max(ans, entry.second);
        } // area of first id
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 0) {
                    int l = j > 0 ? grid[i][j - 1] : 0;
                    int r = j < n - 1 ? grid[i][j + 1] : 0;
                    int u = i > 0 ? grid[i - 1][j] : 0;
                    int d = i < n - 1 ? grid[i + 1][j] : 0;

                    int new_area = 1; // Start with the current 0 being turned into 1
                    if (l > 1) new_area += mp[l];
                    if (r > 1 && r != l) new_area += mp[r];
                    if (u > 1 && u != l && u != r) new_area += mp[u];
                    if (d > 1 && d != l && d != r && d != u) new_area += mp[d];

                    ans = max(ans, new_area);
                }
            }
        }

        return ans;
    }
};
61115