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

&nbsp;
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.


&nbsp;
Constraints:


	1 &lt;= m, n &lt;= 150
	mat[i][j] is either 0 or 1.


class Solution:
    def numSubmat(self, mat: List[List[int]]) -> int:
        from dataclasses import dataclass
        @dataclass
        class Cell:
            left: int = 0
            top: int = 0
            
        n = len(mat)
        m = len(mat[0])  
        dp = [[Cell() for _ in range(m + 1)] for _ in range(n + 1)]
        
        ans = 0
        for i in range(1, n + 1):
            for j in range(1, m + 1):
                if mat[i - 1][j - 1]: 
                    dp[i][j].top = 1 + dp[i - 1][j].top
                    dp[i][j].left = 1 + dp[i][j - 1].left
                    
                    min_height = dp[i][j].top
                    for k in range(dp[i][j].left):
                        min_height = min(min_height, dp[i][j-k].top)
                        ans += min_height 
        return ans
class Solution {
	public int numSubmat(int[][] mat) {
		int n = mat.length;
		int m = mat[0].length;
		//left[i][j] indicates how many consecutive 1s are on the left of i, j
		//left[i][j] indicates how many consecutive 1s are above i, j
		//dp[i][j] represents the number of submatrices with i, j as the lower right corner
		int[][] left = new int[n][m];
		int[][] up = new int[n][m];
		int[][] dp = new int[n][m];
		up[0][0] = mat[0][0];
		left[0][0] = mat[0][0];
		dp[0][0] = mat[0][0];
		for(int i = 1; i < n; i++){
			if(mat[i][0] == 0){
				continue;
			}
			up[i][0] = mat[i][0];
			left[i][0] = left[i - 1][0] + 1;
			dp[i][0] = left[i][0];
		}

		for(int j = 1; j < m; j++){
			if(mat[0][j] == 0){
				continue;
			}
			up[0][j] = up[0][j - 1] + 1;
			left[0][j] = mat[0][j];
			dp[0][j] = up[0][j];
		}

		for(int i = 1; i < n; i++){
			for(int j = 1; j < m; j++){
				if(mat[i][j] == 0){
					continue;
				}
				up[i][j] = up[i][j - 1] + 1;
				left[i][j] = left[i - 1][j] + 1;
				int minHeight = up[i][j];
				for(int k = 0; k < left[i][j]; k++){
					minHeight = Math.min(minHeight, up[i - k][j]);
					dp[i][j] += minHeight;
				}
			}
		}
		int res = 0;
		for(int i = 0; i < n; i++){
			for(int j = 0; j < m; j++){
				res += dp[i][j];
			}
		}
		return res;
	}
}
class Solution {
public:
    int numSubmat(vector<vector<int>>& mat) {
        int n = mat.size(), m = mat[0].size();
        vector<vector<int>> v(n,vector<int>(m+1,0));
        for(int i=0; i<n; i++){
            for(int j=0; j<m; j++){
                v[i][j+1] = v[i][j] + mat[i][j];
            }
        }
        int res = 0;
        for(int i=0; i<m; i++){
            for(int j=i+1; j<=m; j++){
                int cnt = 0;
                for(int k=0; k<n; k++){
                    int x = v[k][j] - v[k][i];
                    if(x == (j-i)){
                        cnt++;
                    }else{
                        res += cnt*(cnt+1)/2;
                        cnt = 0;
                    }
                }
                res += cnt*(cnt+1)/2;
            }
        }
        return res;
    }
};
/**
 * @param {number[][]} mat
 * @return {number}
 */
var numSubmat = function(mat) {
    var m = mat.length;
    var n = mat[0].length;

    for(let i=0; i<m; i++){
        for(let j = n-2; j>=0; j-- ){
            if(mat[i][j] === 0)continue;
            mat[i][j] += mat[i][j+1];

        }
    }
    var sum = 0
    for(let i=0; i<m; i++){
        for(let j = 0; j<n; j++ ){
            if(mat[i][j] === 0)continue;
            var min = mat[i][j]

            for(let k=i; k<m; k++){
                if(mat[k][j] === 0)break;
                min = Math.min(min , mat[k][j])
                sum += min
            }
        }

    }
    return sum
};
Count Submatrices With All Ones