<p>Given an <code>m x n</code> binary matrix <code>mat</code>, <em>return the number of <strong>submatrices</strong> that have all ones</em>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2021/10/27/ones1-grid.jpg" style="width: 244px; height: 245px;" />
<pre>
<strong>Input:</strong> mat = [[1,0,1],[1,1,0],[1,1,0]]
<strong>Output:</strong> 13
<strong>Explanation:</strong> 
There are 6 rectangles of side 1x1.
There are 2 rectangles of side 1x2.
There are 3 rectangles of side 2x1.
There is 1 rectangle of side 2x2. 
There is 1 rectangle of side 3x1.
Total number of rectangles = 6 + 2 + 3 + 1 + 1 = 13.
</pre>

<p><strong class="example">Example 2:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2021/10/27/ones2-grid.jpg" style="width: 324px; height: 245px;" />
<pre>
<strong>Input:</strong> mat = [[0,1,1,0],[0,1,1,1],[1,1,1,0]]
<strong>Output:</strong> 24
<strong>Explanation:</strong> 
There are 8 rectangles of side 1x1.
There are 5 rectangles of side 1x2.
There are 2 rectangles of side 1x3. 
There are 4 rectangles of side 2x1.
There are 2 rectangles of side 2x2. 
There are 2 rectangles of side 3x1. 
There is 1 rectangle of side 3x2. 
Total number of rectangles = 8 + 5 + 2 + 4 + 2 + 2 + 1 = 24.
</pre>

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

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

class Solution {
public:
    int numSubmat(vector<vector<int>>& mat) {
        // return numSubmat_PrefixSum(mat);
        // return numSubmat_PrefixSum2(mat);
        return numSubmat_MonotonicStack(mat);
    }

    int numSubmat_MonotonicStack(const vector<vector<int>>& mat) {  // O(M * N)
        // Enumerate all bottom row of submatrices and for each bottom row i, we count all valid submatrices.
        // In each bottom row, enumerate all bottom right corner, and for each corner we count all valid
        // top left corners, by processing the heights of 1-cells at each (right) column with a monotonic stack.
        // If columns on the left have heights larger or equal than the right column j, then they form a block-J
        // of height h[j] and of length (#leftColNum + 1), whose cells are valid top left corners for the current 
        // bottom right corner (i, j). If column prevIndex is of height smaller than h[j] then its height is a 
        // bottle neck that it and the columns on its left can have at most h[prevIndex] valid left corners.
        // We need to find out the first smaller column (prevIndex) for the currently enumerated right column, 
        // so we use a monotonic stack.
        int m = mat.size(), n = mat[0].size(), ans = 0;
        vector<int> h(n, 0);
        for (int i = 0; i < m; i++) {  // count submatrices having bottom at row i
            stack<pair<int, int>> stk;  // (j, sum[j])
            for (int j = 0, sum = 0; j < n; j++) {  // sum := #{celles in blocks in stack} + #{celles in block-j}
                h[j] = mat[i][j] ? h[j] + 1 : 0;
                while (!stk.empty() && h[stk.top().first] >= h[j]) stk.pop();
                if (stk.empty()) {
                    sum = h[j] * (j + 1);  // #{celles in block-j}
                } else {
                    sum = stk.top().second + h[j] * (j - stk.top().first);
                }
                stk.push({j, sum});
                ans += sum;
            }
        }
        return ans;
    }

    int numSubmat_PrefixSum2(const vector<vector<int>>& mat) {  // O(M * M * N)
        int m = mat.size(), n = mat[0].size(), ans = 0;
        for (int i = 0; i < m; i++) {
            vector<int> validCol(n, 1);
            for (int h = 1; i + h <= m; h++) {
                bool b = false;
                int sum = 0;
                for (int j = 0; j < n; j++) {
                    validCol[j] &= mat[i + h - 1][j];
                    if (validCol[j]) b = true;
                    sum = validCol[j] ? sum + 1 : 0;
                    ans += sum;
                }
                if (!b) break;
            }
        }
        return ans;
    }

    int numSubmat_PrefixSum(const vector<vector<int>>& mat) {  // O(M * M * N)
        int m = mat.size(), n = mat[0].size();
        auto count = [](const vector<int>& arr) -> int {
            int sum = 0, cnt = 0;
            for (int j = 0; j < arr.size(); j++) {
                sum = arr[j] ? sum + 1 : 0;
                cnt += sum;
            }
            return cnt;
        };
        // Enumerate all row intervals and for each row interval we count valid col interval 
        // such that valid a submatrix can be formed with cells inside the row & col intervals.
        int ans = 0;
        for (int i = 0; i < m; i++) {  // testing row interval starts at row i
            vector<int> validCol(n, 1);
            for (int h = 1; i + h <= m; h++) {  // of height h, then count all valid col intervals
                bool b = false;
                for (int j = 0; j < n; j++)
                    validCol[j] &= mat[i + h - 1][j], b |= (bool)validCol[j];
                if (!b) break;
                ans += count(validCol);
            }
        }
        return ans;
    }
};
19300