Today I have done leetcode's August LeetCoding Challenge with cpp.

August LeetCoding Challenge 21

Description

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.

Solution

class Solution {
public:
  int numSubmat(vector<vector<int>>& mat) {
    int rows = mat.size();
    int cols = mat.front().size();
    int answer = 0;
    vector<int> height(cols);
    for(int i = 0 ; i < rows; ++i) {
      for(int j = 0; j < cols; ++j) {
        height[j] = mat[i][j] ? height[j] + 1 : 0;
      }
      vector<int> sum(cols);
      vector<int> st;
      for(int j = 0; j < cols; ++j) {
        while(st.size() && height[st.back()] >= height[j]) st.pop_back();
        if(st.size()) {
          int p = st.back();
          sum[j] = sum[p] + height[j] * (j - p);
        } else {
          sum[j] = height[j] * (j + 1);
        }
        st.push_back(j);
        answer += sum[j];
      }
    }
    return answer;
  }
};

// Accepted
// 73/73 cases passed (0 ms)
// Your runtime beats 100 % of cpp submissions
// Your memory usage beats 26.41 % of cpp submissions (19.8 MB)