<p>You are given an <code>m x n</code> binary matrix <code>grid</code>. An island is a group of <code>1</code>&#39;s (representing land) connected <strong>4-directionally</strong> (horizontal or vertical.) You may assume all four edges of the grid are surrounded by water.</p>

<p>The <strong>area</strong> of an island is the number of cells with a value <code>1</code> in the island.</p>

<p>Return <em>the maximum <strong>area</strong> of an island in </em><code>grid</code>. If there is no island, return <code>0</code>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2021/05/01/maxarea1-grid.jpg" style="width: 500px; height: 310px;" />
<pre>
<strong>Input:</strong> grid = [[0,0,1,0,0,0,0,1,0,0,0,0,0],[0,0,0,0,0,0,0,1,1,1,0,0,0],[0,1,1,0,1,0,0,0,0,0,0,0,0],[0,1,0,0,1,1,0,0,1,0,1,0,0],[0,1,0,0,1,1,0,0,1,1,1,0,0],[0,0,0,0,0,0,0,0,0,0,1,0,0],[0,0,0,0,0,0,0,1,1,1,0,0,0],[0,0,0,0,0,0,0,1,1,0,0,0,0]]
<strong>Output:</strong> 6
<strong>Explanation:</strong> The answer is not 11, because the island must be connected 4-directionally.
</pre>

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

<pre>
<strong>Input:</strong> grid = [[0,0,0,0,0,0,0,0]]
<strong>Output:</strong> 0
</pre>

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

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

class UnionFind {
  public:
    vector < int > parent;
    vector < int > rank;

    // Initializing the parent list and count variable by traversing the grid
    UnionFind(vector < vector < int >> grid) 
    {
      int m = grid.size(), n = grid[0].size();
      for (int i = 0; i < m; i++) 
      {
        for (int j = 0; j < n; j++) 
        {
            parent.push_back(i * n + j);
            rank.push_back(grid[i][j]);
        }
      }
    }

    // Function to find the root parent of a node       
    int Find(int i) 
    {
      if (parent[i] != i)
        parent[i] = Find(parent[i]);
      
      return parent[i];
    }

    // Function to connect components
    void Union(int x, int y) 
    {
      int rootX = Find(x);
      int rootY = Find(y);
      if (rootX != rootY) 
      {
        //The absolute value of the root node represents the size of this union
        //Make the one with larger size to be the new parent
        if (rank[rootX] > rank[rootY])
        {
            parent[rootY] = rootX;
            rank[rootX] += rank[rootY];
        }
        else
        {
            parent[rootX] = rootY;
            rank[rootY] += rank[rootX];
        }
      }
    }
};

class Solution {
public:
    int maxAreaOfIsland(vector<vector<int>>& grid) {
        if (grid[0].size() == 0)
        return 0;
  
        int cols = grid[0].size();
        int rows = grid.size();
        UnionFind unionFind(grid);
        
        int ans = 0;

        for (int r = 0; r < rows; r++) 
        {
            for (int c = 0; c < cols; c++) 
            {
                if (grid[r][c] == 1) 
                {
                    if (r - 1 >= 0 && grid[r - 1][c] == 1)
                    unionFind.Union(r * cols + c, (r - 1) * cols + c);
                    
                    if (r + 1 < rows && grid[r + 1][c] == 1) 
                    unionFind.Union(r * cols + c, (r + 1) * cols + c);
                    
                    if (c - 1 >= 0 && grid[r][c - 1] == 1) 
                    unionFind.Union(r * cols + c, r * cols + c - 1);
                    
                    if (c + 1 < cols && grid[r][c + 1] == 1) 
                    unionFind.Union(r * cols + c, r * cols + c + 1);
                    
                    int p = unionFind.Find(r*cols+c);
                    ans = max(ans, unionFind.rank[p]);
                }
            }
        }
        return ans;
    }
};
29610