<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 Solution {

private: 

    vector<vector<int>> _vGraph;
    vector<vector<bool>> _vSeen;

    vector<vector<int>> _vDirections = { {0,1} , {1,0} , {0,-1} , {-1,0}  };

    int _rows;
    int _cols;

    int _area = 0;

public:

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

        // O(N*M) Time complexity.
        // O(N*M) Space complexity.

        this->_vGraph = grid;
        this->_rows = grid.size();
        this->_cols = grid[0].size();
        this->_vSeen = vector(this->_rows, vector(this->_cols, false));

        int answer = 0;

        for(int i = 0 ; i < this->_rows ; i++) {
            for(int j = 0 ; j < this->_cols ; j++) {
                if(this->isIsland(i,j) && !this->_vSeen[i][j]) {
                    this->_vSeen[i][j] = true;
                    this->iterativeDFS(i,j);
                    answer = max(answer,this->_area);
                    this->_area = 0;
                }
            }
        }

        return answer;
    }

    void iterativeDFS(int row , int col) {

       

        stack<pair<int,int>> myStack;
        myStack.push(pair(row,col));

        while(!myStack.empty()) {

        this->_area++;

        auto [r,c] = myStack.top();
        myStack.pop();

        for(vector<int> &vDirection : this->_vDirections) {

            int nextRow = r + vDirection[0];
            int nextCol = c + vDirection[1];

            if(this->isValidIslandIndex(nextRow,nextCol) && this->isIsland(nextRow,nextCol) && !this->_vSeen[nextRow][nextCol]) {
                this->_vSeen[nextRow][nextCol] = true;
                myStack.push(pair(nextRow,nextCol));        
            }
        }

        }

    }

    bool isValidIslandIndex(int row , int col) {

        bool isValidRow = row >= 0 && row < this->_rows;
        bool isValidCol = col >= 0 && col < this->_cols;

        return isValidRow && isValidCol;
    }

    bool isIsland(int row , int col) {
        return this->_vGraph[row][col] == 1;
    }   


};
33250