<p>Given an <code>m x n</code> binary <code>matrix</code> filled with <code>0</code>&#39;s and <code>1</code>&#39;s, <em>find the largest square containing only</em> <code>1</code>&#39;s <em>and return its area</em>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2020/11/26/max1grid.jpg" style="width: 400px; height: 319px;" />
<pre>
<strong>Input:</strong> matrix = [[&quot;1&quot;,&quot;0&quot;,&quot;1&quot;,&quot;0&quot;,&quot;0&quot;],[&quot;1&quot;,&quot;0&quot;,&quot;1&quot;,&quot;1&quot;,&quot;1&quot;],[&quot;1&quot;,&quot;1&quot;,&quot;1&quot;,&quot;1&quot;,&quot;1&quot;],[&quot;1&quot;,&quot;0&quot;,&quot;0&quot;,&quot;1&quot;,&quot;0&quot;]]
<strong>Output:</strong> 4
</pre>

<p><strong class="example">Example 2:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2020/11/26/max2grid.jpg" style="width: 165px; height: 165px;" />
<pre>
<strong>Input:</strong> matrix = [[&quot;0&quot;,&quot;1&quot;],[&quot;1&quot;,&quot;0&quot;]]
<strong>Output:</strong> 1
</pre>

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

<pre>
<strong>Input:</strong> matrix = [[&quot;0&quot;]]
<strong>Output:</strong> 0
</pre>

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

<ul>
	<li><code>m == matrix.length</code></li>
	<li><code>n == matrix[i].length</code></li>
	<li><code>1 &lt;= m, n &lt;= 300</code></li>
	<li><code>matrix[i][j]</code> is <code>&#39;0&#39;</code> or <code>&#39;1&#39;</code>.</li>
</ul>

class Solution {
public:
// int solve(vector<vector<char>>& matrix,int row,int col,int &maxi,vector<vector<int>>&dp){
//     if(row>=matrix.size() || col>=matrix[0].size()){
//         return 0;
//     }
//     if(dp[row][col]!=-1){
//         return dp[row][col];
//     }
  
//    int down=solve(matrix,row+1,col,maxi,dp);
//    int diagonal=solve(matrix,row+1,col+1,maxi,dp);
//    int right=solve(matrix,row,col+1,maxi,dp);
//    if(matrix[row][col]=='1'){
//    int ans=1+min(right,min(diagonal,down));
//     maxi=max(ans,maxi);
//     dp[row][col]=ans;
//     return ans;
//    }
//    else{
//     return 0;
//    }
  
// }



// void solvetab(vector<vector<char>>& matrix,int row,int col,int &maxi){
//     vector<vector<int>>dp(row+1,vector<int>(col+1,0));
//     for(int i=row-1;i>=0;i--){
//         for(int j=col-1;j>=0;j--){
//              int down=dp[i+1][j];
//              int diagonal=dp[i+1][j+1];
//              int right=dp[i][j+1];
//              if(matrix[i][j]=='1'){
//                 int ans=1+min(right,min(diagonal,down));
//                 maxi=max(ans,maxi);
//                 dp[i][j]=ans;
//     }
//     }
        
//     }

    

// }
void solveSO(vector<vector<char>>& matrix, int &maxi) {
    int row = matrix.size();
    int col = matrix[0].size();

    vector<int> next(col + 1, 0); // Represents the next row in the dp array

    // Iterate from the bottom-right to top-left
    for (int i = row - 1; i >= 0; i--) {
        int right = 0; // Initialize 'right' for the current row
        for (int j = col - 1; j >= 0; j--) {
            int newRight = next[j]; // Store the current value of next[j] to update 'right' later
            
            // If the current cell is '1'
            if (matrix[i][j] == '1') {
                int down = next[j];         // Value from the next row (downwards)
                int diagonal = next[j + 1]; // Value from the next row and next column (diagonally)

                // Compute the size of the square that can be formed
                int ans = 1 + min({right, diagonal, down});
                
                // Update the maximum square size found so far
                maxi = max(ans, maxi);

                // Update the current dp cell
                next[j] = ans;

                // Update the right value to be used in the next iteration (previous column in the current row)
                right = newRight;
            } else {
                // If matrix[i][j] is '0', no square can be formed
                next[j] = 0;
                right = 0; // Reset 'right' because no square can be formed
            }
        }
    }
}


    int maximalSquare(vector<vector<char>>& matrix) {
        int maxi=0;
        int row=matrix.size();
        int col=matrix[0].size();
        solveSO(matrix,maxi);
        return maxi*maxi;
    }
};
22400