<p>Given a <code>rows x cols</code>&nbsp;binary <code>matrix</code> filled with <code>0</code>&#39;s and <code>1</code>&#39;s, find the largest rectangle containing only <code>1</code>&#39;s and return <em>its area</em>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2020/09/14/maximal.jpg" style="width: 402px; height: 322px;" />
<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> 6
<strong>Explanation:</strong> The maximal rectangle is shown in the above picture.
</pre>

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

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

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

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

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

<ul>
	<li><code>rows == matrix.length</code></li>
	<li><code>cols == matrix[i].length</code></li>
	<li><code>1 &lt;= row, cols &lt;= 200</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:

   vector<vector<int>> dp;

int f(int ind) {
    int m = dp[0].size();
    vector<int> pf(m, 0);  // Distance to the left bound (inclusive)
    vector<int> sf(m, 0);  // Distance to the right bound (inclusive)
    stack<int> st;

    // Calculate prefix (pf) - distance to the nearest smaller height on the left
    st.push(-1);  // A dummy index to handle the left bound
    for (int i = 0; i < m; i++) {
        while (st.top() != -1 && dp[ind][st.top()] >= dp[ind][i]) {
            st.pop();
        }
        pf[i] = i - st.top();  // Distance to the left (inclusive)
        st.push(i);
    }

    // Clear the stack for suffix (sf) calculation
    while (!st.empty()) { st.pop(); }

    // Calculate suffix (sf) - distance to the nearest smaller height on the right
    st.push(m);  // A dummy index to handle the right bound
    for (int i = m - 1; i >= 0; i--) {
        while (st.size()>1 && dp[ind][st.top()] >= dp[ind][i]) {
            st.pop();
        }
        sf[i] = st.top() - i;  // Distance to the right (inclusive)
        st.push(i);
    }

    // Calculate the maximum area for the current row
    int maxi = 0;
    for (int i = 0; i < m; i++) {
        if (dp[ind][i] > 0) {  // Only calculate area for non-zero heights
            int height = dp[ind][i];  // Current histogram height
            int width = pf[i] + sf[i] - 1;  // Total width
            maxi = max(maxi, width * height);  // Calculate area and maximize it
        }
    }
    return maxi;
}

int maximalRectangle(vector<vector<char>>& matrix) {
    if (matrix.empty()) return 0;  // Edge case when matrix is empty

    int n = matrix.size();
    int m = matrix[0].size();
    dp.resize(n, vector<int>(m, 0));

    // Build the dp array (heights of histograms)
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            int c = (matrix[i][j] - '0');
            dp[i][j] = c;
            if (i > 0 && dp[i][j] > 0) {
                dp[i][j] += dp[i - 1][j];  // Accumulate the height if the cell is 1
            }
        }
    }

    // Find the maximal rectangle for each row's histogram
    int ans = 0;
    for (int i = 0; i < n; i++) {
        ans = max(ans, f(i));  // Maximize over all rows
    }

    return ans;
}


};
20324