21_Count_Submatrices_With_All_Ones.cpp

// 1504. Count Submatrices With All Ones

// Given an m x n binary matrix mat, return the number of submatrices that have all ones.

 

// Example 1:


// Input: mat = [[1,0,1],[1,1,0],[1,1,0]]
// Output: 13
// Explanation: 
// 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.
// Example 2:


// Input: mat = [[0,1,1,0],[0,1,1,1],[1,1,1,0]]
// Output: 24
// Explanation: 
// 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.
 

// Constraints:

// 1 <= m, n <= 150
// mat[i][j] is either 0 or 1.

class Solution
{
public:
    int numSubmat(vector<vector<int>> &mat)
    {
        int r = mat.size(), c = mat[0].size(), ans = 0;
        vector<int> h(c);
        for (int i = 0; i < r; i++)
        {
            for (int j = 0; j < c; j++)
                h[j] = mat[i][j] ? h[j] + 1 : 0;
            vector<int> sum(c);
            stack<int> st;
            for (int j = 0; j < c; j++)
            {
                while (!st.empty() && h[st.top()] >= h[j])
                    st.pop();
                if (!st.empty())
                {
                    int p = st.top();
                    sum[j] = sum[p] + h[j] * (j - p);
                }
                else
                {
                    sum[j] = h[j] * (j + 1);
                }
                st.push(j);
                ans += sum[j];
            }
        }
        return ans;
    }
};