Given a rows * columns matrix mat of ones and zeros, return how many submatrices 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.

Example 3:
Input: mat = [[1,1,1,1,1,1]]
Output: 21

Example 4:
Input: mat = [[1,0,1],[0,1,0],[1,0,1]]
Output: 5

 
Constraints:

1 <= rows <= 150
1 <= columns <= 150
0 <= mat[i][j] <= 1

Difficulty: interview

Starter code:

class Solution:
    def numSubmat(self, mat: List[List[int]]) -> int:
        

Solutions:
class Solution:
    def numSubmat(self, mat: List[List[int]]) -> int:
        n, m = len(mat), len(mat[0])
        heights = [0] * m
        res = 0
        for i in range(0, n):
            stack = []
            count = 0
            for j in range(0, m):
                if mat[i][j] == 1:
                    heights[j] += 1
                else:
                    heights[j] = 0
            for index, height in enumerate(heights):
                while stack and height < heights[stack[-1]]:
                    curr = stack.pop()
                    left = stack[-1] if stack else -1
                    count -= (heights[curr] - height) * (curr - left)
                count += height
                res += count
                stack.append(index)
        return res
            


class Solution:
    def numSubmat(self, matrix):
        m, n = len(matrix), len(matrix[0])
        res = 0
        heights = [0] * (n + 1)
        for x in range(m):
            stack = []
            dp = [0] * (n + 1)
            for y in range(n):
                if matrix[x][y] == 1:
                    heights[y] = heights[y] + 1
                else:
                    heights[y] = 0
            for right in range(n + 1):
                while stack and heights[right] <= heights[stack[-1]]:
                    cur = stack.pop()
                if stack:
                    left = stack[-1]
                    dp[right] = dp[left] + heights[right] * (right - left) 
                else:
                    left = -1
                    dp[right] = heights[right] * (right - left) 
                stack.append(right)
            res += sum(dp)
        return res


class Solution:
    def numSubmat(self, mat):

        if not mat:
            return 0

        for i in range(len(mat)):
            for j in range(1, len(mat[0])):
                mat[i][j] = 1 + mat[i][j-1] if mat[i][j] !=0 else 0

        for j in range(len(mat[0])):
            stack = [(-1, -1)] # index, value
            for i in range(len(mat)):
                while stack and mat[i][j] < stack[-1][1]:
                    stack.pop()
                stack.append((i, mat[i][j]))
                mat[i][j] = mat[i][j] * (i - stack[-2][0]) + (mat[stack[-2][0]][j] if stack[-2][0] != -1 else 0)

        return sum([sum(arr) for arr in mat])

class Solution:
    def numSubmat(self, mat: List[List[int]]) -> int:
        # udpate mat to histogram
        row = len(mat)
        col = len(mat[0])
        for j in range(col):
            for i in range(1, row):
                mat[i][j] = mat[i - 1][j] + 1 if mat[i][j] == 1 else 0 
        
        total = 0
        for i in range(row):
            for j in range(col):
                if mat[i][j] == 0:
                    continue
                cur = j
                delta = 0
                min_h = float('inf')
                while cur >= 0 and mat[i][cur] != 0:
                    cur_h_above = mat[i - 1][cur] if i - 1 >= 0 else 0
                    min_h = min(min_h, cur_h_above)
                    delta += (min_h + 1)
                    cur -= 1
                total += delta
        return total

class Solution:
    def numSubmat(self, mat: List[List[int]]) -> int:
        rows = len(mat)
        columns = len(mat[0])
        def countSubmat(s_r, s_c):
            e_r = rows
            e_c = columns
            c_r = s_r
            c_c = s_c
            count = 0
            while c_r < e_r:
                if mat[c_r][s_c] == 0:
                    break
                else:
                    count += 1
                    c_c = s_c + 1
                while c_c < e_c:
                    if mat[c_r][c_c] == 1:
                        count += 1
                    else:
                        e_c = c_c
                    c_c += 1
                c_r += 1
                c_c = s_c
            return count
        res = 0
        for i in range(rows):
            for j in range(columns):
                res += countSubmat(i, j)
        return res
                    
            


class Solution:
    def numSubmat(self, mat: List[List[int]]) -> int:
        if not mat:
            return 0
        m, n = len(mat), len(mat[0])
        prefix = [[0] * n for _ in range(m)]
        for i in range(m):
            for j in range(n - 1, -1, -1):
                if j == n - 1:
                    prefix[i][j] = mat[i][j]
                if mat[i][j] == 0:
                    continue
                if j + 1 <= n - 1:
                    prefix[i][j] = prefix[i][j + 1] + mat[i][j]
        print(prefix)
        count =  [[0] * n for _ in range(m)]  
        for i in range(m):
            for j in range(n):
                width = prefix[i][j]
                res = width
                for k in range(i + 1, m):
                    if prefix[k][j] <= width:
                        width = prefix[k][j]
                        res += prefix[k][j]
                    else:
                        res += width
                count[i][j] = res
        print(count)
        ans = 0
        for i in range(m):
            ans += sum(count[i])
        
        return ans
                    
                    
                    


class Solution:
    def numSubmat(self, mat: List[List[int]]) -> int:
        res = 0
        m, n = len(mat), len(mat[0])
        
        dp = [[0 for j in range(n)] for i in range(m)]
        # width of contnuous ones in row i and ends at mat[i][j]
        
        for i in range(m):
            for j in range(n):
                if mat[i][j]:
                    if j == 0:
                        dp[i][j] = 1
                    else:
                        dp[i][j] = dp[i][j-1] + 1
        
        for i in range(m):
            for j in range(n):
                if mat[i][j] == 0:
                    continue
                row, minwidth = i, float('inf')
                while row >= 0 and mat[row][j]:
                    minwidth = min(minwidth, dp[row][j])
                    res += minwidth
                    row -= 1
                    
        return res

class Solution:
    def numSubmat(self, mat: List[List[int]]) -> int:
        R, C = len(mat), len(mat[0])
        hist = [[0] * C for _ in range(R)]
        
        for r in range(R):
            for c in range(C):
                if mat[r][c]:
                    hist[r][c] = 1 if r == 0 else hist[r-1][c] + 1
        
        ret = 0
        for row in hist:
            all_stacks = []
            stack = []
            for num in row:
                if num > 0:
                    stack.append(num)
                elif stack:
                    all_stacks.append(stack[::])
                    stack = []
            if stack:
                all_stacks.append(stack)
            
            for stack in all_stacks:
                while stack:
                    last_h = stack[-1]
                    minsofar = last_h
                    for h in stack[::-1]:
                        minsofar = min(minsofar, h)
                        ret += minsofar
                    stack.pop()
            
        
        return ret


class Solution:
    def numSubmat(self, mat: List[List[int]]) -> int:
        if not mat: return 0
        
        m, n = len(mat), len(mat[0])
        
        count = 0
        for i in range(m):
            for j in range(n):
                if mat[i][j] == 1:
                    count += 1
                    up, left = i - 1, j - 1
                    
                    while up >= 0 and mat[up][j] == 1: up -= 1
                    count += i - up - 1
                    
                    while left >= 0 and mat[i][left] == 1: left -= 1
                    count += j - left - 1
                    
                    print(i, j, up, left)
                    k = i - 1
                    while k > up:
                        l = j - 1
                        if mat[k][l] == 0: break
                        while l > left:
                            if mat[k][l] == 1: 
                                count += 1
                                l -= 1
                            else: 
                                left = l
                                break
                        k -= 1
        return count

class Solution:
    def numSubmat(self, mat: List[List[int]]) -> int:
        m, n = len(mat), len(mat[0])
        res = 0
        for i in range(len(mat)):
            for j in range(len(mat[0])):
                if mat[i][j] == 1: # this could be a top-left
                    right_edge = n
                    for res_i in range(i, m):
                        if mat[res_i][j] == 0:
                            break
                        for res_j in range(j, right_edge):
                            if mat[res_i][res_j] == 1:
                                res += 1
                            else:
                                right_edge = min(right_edge, res_j)
                                break
        return res

from math import floor
from math import ceil
from math import sqrt
from collections import deque
import numpy
from _collections import deque
#from _ast import Num # LC doesn't like this
from heapq import *
from typing import List
import random

MOD = int(1e9 + 7)
BASE = 256


class Solution:

    def numSubmat(self, mat: List[List[int]]) -> int:
        R = len(mat)
        if not R:
            return 0
        C = len(mat[0])

        ans = [[0 for _ in range(C)] for _ in range(C)]

        cnt = 0

        for i in range(R):
            nextAns = [[0 for _ in range(C)] for _ in range(C)]
            last0j = -1
            for j in range(C):
                if not mat[i][j]:
                    last0j = j

                for si in range(last0j + 1, j + 1):
                    nextAns[j][si] = ans[j][si] + 1
                    cnt += nextAns[j][si]
                    #print(cnt, j, si)
            ans = nextAns

        return cnt

\"\"\"
S = Solution()
mat = [[1, 1]]
mat = [[1, 0, 1], [1, 1, 0], [1, 1, 0]]
mat = [[0, 1, 1, 0], [0, 1, 1, 1], [1, 1, 1, 0]]
mat = [[1, 1, 1, 1, 1, 1]]
mat = [[1, 0, 1], [0, 1, 0], [1, 0, 1]]
print(S.numSubmat(mat))
\"\"\"


class Solution:
    def numSubmat(self, mat: List[List[int]]) -> int:
        
        nrows = len(mat)
        ncols = len(mat[0])
        
        for i in range(nrows):
            for j in range(ncols):
                if mat[i][j]:
                    if j > 0:
                        mat[i][j] = mat[i][j - 1] + 1
        
        cnt = 0
        
        for i in range(nrows):
            for j in range(ncols):
                if mat[i][j]:
                    row = i
                    submatrix_width = mat[i][j]
                    
                    while row < nrows and mat[row][j]:
                        submatrix_width = min(submatrix_width, mat[row][j])
                        cnt += submatrix_width
                        row += 1
        return cnt


                


class Solution:
    def numSubmat(self, mat: List[List[int]]) -> int:
        rows = len(mat)
        columns = len(mat[0])
        count = 0
        for i in range(rows):
            for j in range(columns):
                width = columns
                for y in range(i, rows):
                    if mat[y][j] == 0:
                        break
                    for x in range(j, width):
                        if mat[y][x] == 0:
                            width = x
                            break
                        count += 1
        return count

\"\"\"
用increasing monostack找到以(i, j)结尾的全为1的最大rectangle, 就很容易计算以(i, j)结尾submatrices的个数了.
\"\"\"
class Solution:
    def numSubmat(self, matrix: List[List[int]]) -> int:
        m, n = len(matrix), len(matrix[0])
        for i in range(1, m):
            for j in range(n):
                if matrix[i][j] == 1:
                    matrix[i][j] += matrix[i-1][j]  # construct the histogram 
                
        res = 0
        for i in range(m):
            res += self._histogram(matrix[i])       # helper function return the total cnt of row i
        return res
        
    def _histogram(self, heights):
        \"\"\"
        算法核心是：以j结尾的submatrices的个数等于heights[j] * (j - 向左找第一个height小于heights[j]的idx)
        算法是84.Largest-Rectangle-in-Histogram, 85.Maximal-Rectangle. we need maintain an increasing stack
        \"\"\"
        cnt = [0 for _ in range(len(heights))]
        st = []
        for j, height in enumerate(heights):
            while len(st) > 0 and st[-1][0] >= height:
                st.pop()
                
            if len(st) == 0:
                cnt[j] = height * (j + 1)
            else:
                cnt[j] = height * (j - st[-1][1]) + cnt[st[-1][1]]
                
            st.append((height, j))

        return sum(cnt)

class Solution:
    def numSubmat(self, mat: List[List[int]]) -> int:
        M, N = len(mat), len(mat[0])

        def count_submatrices(a, b):
            count, bound = 0, N

            for i in range(a,M):
                y = b
                while y < bound:
                    if mat[i][y]:
                        count += 1
                    else:
                        bound = y
                    y += 1
            return count

        count = 0
        for i in range(M):
            for j in range(N):
                count += count_submatrices(i, j)
        return count




class Solution:
    def numSubmat(self, mat: List[List[int]]) -> int:
        m, n = len(mat), len(mat[0])
        res = 0
        for j in range(n):
            for i in range(1, m):
                if mat[i][j]:
                    mat[i][j] += mat[i-1][j]
        print(mat)
        for j in range(n-1, -1, -1):
            for i in range(m):
                if mat[i][j]:
                    minval = mat[i][j]
                    for k in range(j - 1, -1, -1):
                        if mat[i][k] == 0:
                            break
                        minval = min(minval, mat[i][k])
                        mat[i][j] += minval
                res += mat[i][j]
        print(mat)

        return res


from functools import lru_cache

class Solution:
    def numSubmat(self, mat: List[List[int]]) -> int:
        
        n = len(mat)
        m = len(mat[0])
        
        total = 0
        for i in range(n):
            for j in range(m):
                bound = m
                for k in range(i, n):
                    l = j
                    while l < bound:
                        if mat[k][l]: 
                            total += 1
                            l += 1
                        else:
                            bound = l
        return total

class Solution:
    def numSubmat(self, mat: List[List[int]]) -> int:
        count = 0
        for i in range(len(mat)):
            for j in range(len(mat[i])):
                if(mat[i][j]==1):
                    #print('pos 0: ',i, ', ', j)
                    count += 1
                    down = 0
                    right = 0
                    for x in range(i+1,len(mat)):
                        if(mat[x][j]!=1):
                            break
                        #print(x, ', ',j)
                        count += 1
                        down += 1
                    for x in range(j+1,len(mat[i])):
                        if(mat[i][x]!=1):
                            break
                        #print(i,', ',x)
                        count += 1
                        right += 1
                    if(down>0 and right>0):
                        for x in range(1,down+1):
                            for y in range(1,right+1):
                                if(mat[i+x][j+y]!=1):
                                    right = y-1
                                    break
                                #print(i+x,', ',j+y)
                                count += 1
        return(count)


class Solution:
    def numSubmat(self, mat: List[List[int]]) -> int:
        m = len(mat)
        n = len(mat[0])
        rows = []
        for row in mat:
            cur = [0]
            for x in row:
                cur.append(cur[-1] + x)
            rows.append(cur)
            
        res = 0
        for j2 in range(1, n+1):
            for j1 in range(j2):
                width = j2 - j1
                pre_idx = -1
                cur = 0
                for i in range(m):
                    if rows[i][j2] - rows[i][j1] != width:
                        pre_idx = i
                    else:
                        res += i - pre_idx
        return res


class Solution:
    def numSubmat(self, mat: List[List[int]]) -> int:
        M=len(mat)
        N=len(mat[0])
        res=0       
        
        for top in range(M):
            for left in range(N):
                bound=N
                for bottom in range(top,M):                    
                    right=left
                    while right<bound:
                        if mat[bottom][right]==1:
                            res+=1
                            right+=1
                        else:
                            bound=right
                            break
                            

        return res                  
                        
                        
                    
                


class Solution:
    def histogramCount(self, histograms):
        stack = []
        count = 0
        out = 0
        for i in range(len(histograms)):
            while len(stack)!= 0 and histograms[i] < histograms[stack[-1]]:
                j = stack.pop()
                if len(stack) == 0:
                    k = -1
                else:
                    k = stack[-1]
                count -= (histograms[j]-histograms[i])*(j-k)
            count += histograms[i]
            out += count
            stack.append(i)
        return out
            
    def numSubmatHard(self, mat: List[List[int]]) -> int:
        prev = [0]*len(mat[0])
        out = 0
        for i in range(len(mat)):
            for j in range(len(mat[i])):
                if mat[i][j] == 0:
                    prev[j] = 0
                else:
                    prev[j] += mat[i][j]
            out += self.histogramCount(prev)
            print(prev, out)
        return out
    
    def memoization(self, grid, i, j, memo):
        if i == len(grid) or j == len(grid[0]):
            return 0, 0, 0
        if memo[i][j] is not None:
            return memo[i][j]
        if grid[i][j] == 0:
            memo[i][j] = 0, 0, 0
        else:
            if i == len(grid)-1:
                _, col, _ = self.memoization(grid, i, j+1, memo)
                memo[i][j] = 1, col+1, col+1
            elif j == len(grid[0])-1:
                row, _, _ = self.memoization(grid, i+1, j, memo)
                memo[i][j] = row+1, 1, row+1
            else:
                rows, _, _ = self.memoization(grid, i+1, j, memo)
                prev = rows + 1
                out = prev
                k = j+1
                while k < len(grid[0]) and grid[i][k] != 0:
                    row, _, _ = self.memoization(grid, i, k, memo)
                    prev = min(prev, row)
                    out += prev
                    k += 1
                memo[i][j] = rows + 1, k - j, out
        return memo[i][j]
    
    def numSubmat(self, mat: List[List[int]]) -> int:
        memo = [[None for j in range(len(mat[0]))] for i in range(len(mat))]
        out = 0
        for i in range(len(mat)):
            for j in range(len(mat[0])):
                _, _, val = self.memoization(mat, i, j, memo)
                out += val
        return out

class Solution:
    def numSubmat(self, mat: List[List[int]]) -> int:
        
        # 1
        
        rows= len(mat)-1
        cols= len(mat[0])-1
        total=0
        
        def find_rects(i,j):
            local=0
            imax=rows+1
            j_cur=j
            while j_cur<=cols:
                if mat[i][j_cur]==0:
                    break
                i_cur=i
                while i_cur<imax:
                    if mat[i_cur][j_cur]==1:
                        i_cur+=1
                    else:
                        break
                imax=min(i_cur,imax)
                local+=(imax-i)
                j_cur+=1
                
            return local
                    
        
        
        for i in range(rows+1):
            for j in range(cols+1):
                if mat[i][j]==1:
                    total+=find_rects(i,j)
        return total

class Solution:
    def numSubmat(self, mat: List[List[int]]) -> int:
        
        if not mat or not mat[0]:
            return 0
        
        m = len(mat)
        n = len(mat[0])
        dp = [[0]*(n+1) for i in range(m+1)]
        
        res = 0
        for i in range(m):
            for j in range(n):
                if mat[i][j] == 1:
                    # dp only counts num from looking left
                    dp[i+1][j+1] = dp[i+1][j] + 1
                    res += dp[i+1][j+1]
                    
                    minOnes = dp[i+1][j+1]
                    k = i-1
                    while k >=0 and mat[k][j] == 1:
                        minOnes = min(minOnes, dp[k+1][j+1])
                        res += minOnes
                        k -= 1
                        
                        
        return res


class Solution:
    def numSubmat(self, mat: List[List[int]]) -> int:
        if not mat:
            return 0
        answer = 0
        row, col = len(mat), len(mat[0])
        # Get the number of 1's to the right of the current 1
        # For example:
        # [1, 0, 1]
        # [1, 1, 0]
        # [1, 1, 0] 
        # turns into
        # [1, 0, 1]
        # [2, 1, 0]
        # [2, 1, 0]
        one_counts = [[0 for _ in range(col)] for _ in range(row)]
        for r in range(row):
            counter = 0
            for c in range(col-1,-1,-1): 
                if mat[r][c] == 1:
                    counter += 1
                    one_counts[r][c] = counter
                else:
                    counter = 0
        # Go through each element in the matrix, and if it is == 1, check how many
        # submatricies with this element as the top leftmost point can we generate 
        for r in range(row):
            for c in range(col):
                if mat[r][c] == 1:
                    min_width = float('inf') 
                    for k in range(r, row):
                        if mat[k][c] == 1:
                            min_width = min(min_width, one_counts[k][c])
                            answer += min_width
                            continue
                        break  
        return answer 

class Solution:
    def numSubmat(self, mat: List[List[int]]) -> int:
        m, n = len(mat), len(mat[0])
        res = 0
        dp = [0] * n
        for r in range(m):
            stack = []
            for c in range(n):
                cnt = 0
                if mat[r][c]:
                    if r > 0:
                        mat[r][c] += mat[r-1][c]
                    while stack and mat[r][stack[-1]] >= mat[r][c]:
                        stack.pop()
                    cnt += (c - (stack[-1] if stack else -1))*mat[r][c]
                    if stack:
                        cnt += dp[stack[-1]]
                stack.append(c)
                dp[c] = cnt
                res += cnt
        return res

class Solution:
    def numSubmat(self, mat: List[List[int]]) -> int:
        rows = len(mat)
        cols = len(mat[0])
        # row_matrices[i][j] = num of submatrices in row i that ends in col j
        row_matrices = [[0] * cols for _ in range(rows)]
        
        # Count submatrices for every single row
        for i in range(rows):
            row_matrices[i][0] = mat[i][0]
            for j in range(1, cols):
                if mat[i][j] == 1:
                    row_matrices[i][j] = row_matrices[i][j - 1] + 1
                else:
                    row_matrices[i][j] = 0
        
        result = 0
        
        for i in range(rows):
            for j in range(cols):
                cur_min = float('inf')
                # Search upwards row by row
                for k in range(i, -1, -1):
                    if mat[k][j] == 0:
                        break
                        
                    # why min():
                    #   0, 1, 1, 1  r0
                    #   0, 0, 1, 1  r1
                    #   0, 1, 1, 1  r2
                    # the num of matrices will be bottlenecked by the row
                    # with minimum matrices. In this case, r1.
                    cur_min = min(cur_min, row_matrices[k][j])
                    result += cur_min
                    
        return result


class Solution:
    def numSubmat(self, mat: List[List[int]]) -> int:
        m, n = len(mat), len(mat[0])
        count = 0
        for left in range(n):
            row_sums = [0 for _ in range(m)]
            for right in range(left, n):
                consec_count = 0
                width = right - left + 1
                for bottom in range(m):
                    row_sums[bottom] += mat[bottom][right]
                    if row_sums[bottom] != width:
                        consec_count = 0
                    else:
                        consec_count += 1
                        count += consec_count
        return count

class Solution:
    
    
    def singlePointSubmat(self,mat,x,y):
        row = len(mat)
        column = len(mat[0])
        
        res = 0
        
        #stoplength store the first zero position\\
        
        stoplength = column - y
        for r in range(row - x):
            if mat[x+r][y] == 1:
                res += 1
            else:
                return res
            for c in range(1,column - y):
                if c >= stoplength:
                    break
                if mat[x+r][y+c] == 1:
                    res += 1
                else:
                    stoplength = c
        return res
                    
    def numSubmat(self, mat: List[List[int]]) -> int:
        
        #check validity
        if len(mat) == 0 or len(mat[0]) == 0:
            return 0
        
        #find border
        
        row = len(mat)
        column = len(mat[0])
        
        result = 0
        
        for r in range(row):
            for c in range(column):
                
                if mat[r][c] == 1:
                    result += self.singlePointSubmat(mat,r,c)
        return result


import copy
from math import sqrt
from typing import List
import numpy

import sys


class Solution:
  def numSubmat(self, mat: List[List[int]]) -> int:
    row = len(mat)
    col = len(mat[0])
    height = [0] * col
    result = 0
    for i in range(row):

      for j in range(col):
        if mat[i][j] == 0:
          height[j] = 0
        else:
          height[j] = height[j] + 1

        k = j
        minvalue = sys.maxsize
        while k >= 0 and height[k] != 0:
          minvalue = min(minvalue, height[k])
          result += minvalue
          k -= 1
        pass
      pass
    return result

class Solution:
    def numSubmat(self, mat: List[List[int]]) -> int:
        
        # 生成直方图histogram
        def countOneRow(arr):
            res = 0
            l = 0
            for i in range(len(arr)):
                if arr[i] == 0:
                    l = 0
                else: l = l + 1
                res += l # 以当前为最右，可以形成l个矩形
            return res
        
        rows = len(mat)
        cols = len(mat[0])
        res = 0
        for top in range(rows):
            h = [1] * cols
            for bottom in range(top, rows):
                for c in range(cols):
                    # 每一行都跟top来merge，因为中间必须所有格都是1，才能形成一个矩形
                    h[c] &= mat[bottom][c]
                res += countOneRow(h)
                if not any(h): break
        return res

class Solution:
    def numSubmat(self, mat: List[List[int]]) -> int:
        
        # 生成直方图histogram
        def countOneRow(arr):
            res = 0
            l = 0
            for i in range(len(arr)):
                if arr[i] == 0:
                    l = 0
                else: l = l + 1
                res += l # 以当前为最右，可以形成l个矩形
            return res
        
        rows = len(mat)
        cols = len(mat[0])
        res = 0
        for top in range(rows):
            h = [1] * cols
            l = 0
            for bottom in range(top, rows):
                for c in range(cols):
                    # 每一行都跟top来merge，因为中间必须所有格都是1，才能形成一个矩形
                    h[c] &= mat[bottom][c]
                res += countOneRow(h)
                if not any(h): break
        return res

class Solution:
    def numSubmat(self, mat: List[List[int]]) -> int:
        m,n = len(mat), len(mat[0])

        
        def compute(h):
          res = 0
          temp = 0 
          for i in range(len(h)):
             if h[i] > 0:
                temp += 1
             else:
                temp = 0
             res += temp
          return res 

        ans = 0 
        for i in range(m):
          h = [1]*n 
          for k in range(i,m):
            for j in range(n):
                 if mat[k][j] == 0:
                    h[j] = 0 
            ans += compute(h)
        return ans   
        

class Solution1:
    def numSubmat(self, mat: List[List[int]]) -> int:
        def countonerow(A):
            res,length = 0,0
            for i in range(len(A)):
                length = 0 if A[i] == 0 else length + 1
                res += length
            return res 
        
        def compute_one_row(arr):
            count = 0
            length = 0
            for a in arr:
                if a == 1:
                    length += 1
                else:
                    length = 0 
                count += length
            return count 
        
        m,n = len(mat), len(mat[0])
        res = 0
        for i in range(m):
            h = [1]*n
            for j in range(i,m):
                for k in range(n):
                    if mat[j][k] == 0:
                        h[k] = 0 
                res += compute_one_row(h)
        return res



    def numSubmat1(self, mat: List[List[int]]) -> int:
        m,n,res=len(mat),len(mat[0]),0
        histogram=[0]*(n+1)
        for i in range(m):
            stack,dp=[-1],[0]*(n+1)
            for j in range(n):
                histogram[j]=0 if mat[i][j]==0 else histogram[j]+1
                while histogram[j]<histogram[stack[-1]]: #increasing stack
                    stack.pop()
                dp[j]=dp[stack[-1]]+histogram[j]*(j-stack[-1]) # Important!!
                stack.append(j)
            res+=sum(dp)
        return res

class Solution:
    def numSubmat(self, a: List[List[int]]) -> int:
        
        '''
            1 0 1
            1 1 0
            1 1 0
            
            -> row0 ~ row0 -> col0 ~ col2 -> 1 x 1: 2
            -> row0 ~ row1 -> col0 ~ col2 -> 1 x 2: 1
            -> row0 ~ row2 -> col0 ~ col2 -> 1 x 3: 1
            -> row1 ~ row1 -> col0 ~ col2 -> 1 x 1: 2
            -> row1 ~ row2 -> col0 ~ col2 -> 1 x 2: 2, 2 x 1: 2, 2 x 2 = 1
            -> row2 ~ row2 -> col0 ~ col2 -> 1 x 1: 2
            
            2 + 1 + 1 + 2 + 2 + 2 + 1 + 2
                = 13                                
        '''
        m = len(a)
        n = len(a[0])
        
        def oneDHelper(A):
            res = 0
            l = 0
            for i in range(0, len(A)):
                if A[i] == 0:
                    l = 0        
                else:
                    l = l + 1        
                res += l                
            return res

        count = 0
        for r1 in range(0, m):            
            isAll1 = a[r1]            
            for r2 in range(r1, m):
                
                for c in range(0, n):
                    if a[r2][c] == 0:
                        isAll1[c] = 0
                
                count += oneDHelper(isAll1)
                                                
        return count
                
                
                    
                    
                    
                    
                    
                
                
                
                          


class Solution:
    def numSubmat(self, mat: List[List[int]]) -> int:
        m, n = len(mat), len(mat[0])
    
        for i in range(m):
            for j in range(n):
                if mat[i][j] and i > 0:
                    mat[i][j] += mat[i-1][j]

        res = 0          
        for i in range(m):
            stack = []
            cnt = 0
            for j in range(n):
                while stack and mat[i][stack[-1]] > mat[i][j]:
                    tmp = stack.pop()
                    left = stack[-1] if stack else -1
                    cnt -= (mat[i][tmp] - mat[i][j]) * (tmp - left)
                cnt += mat[i][j]
                res += cnt
                stack.append(j)
        return res

class Solution:
    def numSubmat(self, mat: List[List[int]]) -> int:
        m, n = len(mat), len(mat[0])
        
        ans = 0
        for left in range(n):
            row_sum = [0 for _ in range(m)]
            for right in range(left, n):
                consec_count = 0
                w = right - left + 1
                for bottom in range(m):
                    row_sum[bottom] += mat[bottom][right]
                    if row_sum[bottom] != w:
                        consec_count = 0
                    else:
                        consec_count += 1
                        ans += consec_count
        return ans

class Solution:
    def countSubMat(self,rowmat:List[int])->int:
        # count=rowmat[0]
        # for i in range(1,len(rowmat)):
        #     rowmat[i]=0 if rowmat[i]==0 else (rowmat[i-1]+rowmat[i])
        #     count+=rowmat[i]
        
        length=0
        count=0
        for i in range(len(rowmat)):
            length=0 if rowmat[i]==0 else (length+1)
            count+=length
        return count
    
    def numSubmat(self, mat: List[List[int]]) -> int:
        count=0
        
        for m in range(len(mat)):
            
            h=[1 for _ in range(len(mat[0]))]
            for down in range(m,len(mat),1):
                for n in range(len(mat[0])):
                    h[n]=h[n]and mat[down][n]
                
                count+=self.countSubMat(h)
                
        return count
        
        #[[1,0,1],[1,1,0],[1,1,0]]
#     def numSubmat(self, mat: List[List[int]]) -> int:
#         count=0
        
#         #filter size
#         for i in range(len(mat)):
#             for j in range(len(mat[0])):
                
#                 #for all position
#                 for a in range(len(mat)):
#                     if a+i<len(mat):
#                         for b in range(len(mat[0])):
#                             if b+j<len(mat[0]):
#                                 tmp=0
                                
#                                 #for position inside filter
#                                 for c in range(a,a+i+1,1):
#                                     for d in range(b,b+j+1,1):
#                                         tmp+=mat[c][d]
                                        
#                                 if tmp==((i+1)*(j+1)):
#                                     count+=1
#         return count
#            #[[1,0,1],[1,1,0],[1,1,0]]             
                        
                        


class Solution:
    def countOnes(self, nums):
        res = 0
        length = 0
        for i in range(len(nums)):
            length = 0 if nums[i] == 0 else length + 1
            res += length
        return res
        
    def numSubmat(self, mat: List[List[int]]) -> int:
        if not mat or not mat[0]:
            return 0
        
        n, m = len(mat), len(mat[0])
        res = 0
        
        for i in range(n):
            h = [1] * m
            
            for j in range(i, n):
                for k in range(m):
                    if mat[j][k] == 0:
                        h[k] = 0
                res += self.countOnes(h)
        
        return res
                


class Solution:
    def numSubmat(self, mat: List[List[int]]) -> int:
        # O(m ^ 2 * n); Space: O(mn)
        # focus on bottom left matrix, look left and look up
        if not mat:
            return 0
        
        m, n = len(mat), len(mat[0])
        
        dp = [[0] * (n + 1) for _ in range(m + 1)]
        
        res = 0
        for i in range(1, m + 1):
            for j in range(1, n + 1):
                if mat[i - 1][j - 1]:
                    dp[i][j] = dp[i][j - 1] + 1 # look left
                    res += dp[i][j]
                    # look above
                    min_ones = dp[i][j]
                    for k in range(i - 1, -1, -1):
                        min_ones = min(min_ones, dp[k][j])
                        res += min_ones
        return res

def scan(arr,height):
    _sum, found = 0, 0
    for x in arr:
        _sum = 0 if x<height else (_sum+1)
        if _sum:
            found += _sum
    return found
class Solution:
    def numSubmat(self, mat: List[List[int]]) -> int:
        r, result = len(mat), 0
        for i in range(r):
            row     = mat[i]
            result += scan(row,1)
            for k in range(i+1,r):
                row = [ x+mat[k][j] for j,x in enumerate(row) ]
                result += scan(row,k-i+1)
        return result


class Solution:
    def scan(self, arr,height):
        _sum, found = 0, 0
        for x in arr:
            _sum = 0 if x<height else (_sum+1)
            if _sum:
                found += _sum
        return found
    
    def numSubmat(self, mat: List[List[int]]) -> int:
        r, result = len(mat), 0
        for i in range(r):
            row     = mat[i]
            result += self.scan(row,1)
            for k in range(i+1,r):
                row = [ x+mat[k][j] for j,x in enumerate(row) ]
                result += self.scan(row,k-i+1)
        return result

# class Solution:
#     def numSubmat(self, mat: List[List[int]]) -> int:
#         n, m = len(mat), len(mat[0])
#         cache = {}
        
#         for rows in range(1, n + 1):
#             for cols in range(1, m + 1):
#                 for i in range(n):
#                     for j in range(m):
                        
#                         if i + rows <= n and j + cols <= m:
#                             if rows == 1 and cols == 1:
#                                 if mat[i][j] == 1:
#                                     cache[(i, j, rows, cols)] = 1
#                             else:
#                                 if rows > 1 and (i, j, rows - 1, cols) in cache and (i + rows - 1, j, 1, cols) in cache:
#                                     cache[(i, j, rows, cols)] = 1

#                                 elif cols > 1 and (i, j, rows, cols - 1) in cache and (i, j + cols - 1, rows, 1) in cache:
#                                     cache[(i, j, rows, cols)] = 1
        
#         return len(cache)

class Solution:
    def numSubmat(self, mat: List[List[int]]) -> int:
        n, m = len(mat), len(mat[0])
        
        def num_submat_at(a, b):
            c = 0
            bound = m
            
            i = a
            while i < n:
                j = b
                while j < bound:
                    if mat[i][j]:
                        c += 1
                    else:
                        bound = j
                    
                    j += 1
                i += 1
            return c
    
        total_c = 0
        for i in range(n):
            for j in range(m):
                total_c += num_submat_at(i, j)

        return total_c

from typing import List


def matrices_in_rect(rows: int, cols: int) -> int:
    return int((cols * (cols + 1) / 2) * (rows * (rows + 1) / 2))


class Solution:
    def numSubmat(self, mat: List[List[int]]) -> int:
        def count_rectangles(start_row: int, start_col: int) -> int:
            rows, cols = len(mat), len(mat[0]) if mat else 0
            count = 0

            max_col = cols

            for row in range(start_row, rows):
                if mat[row][start_col] != 1:
                    break

                for col in range(start_col, max_col):
                    if mat[row][col] != 1:
                        break

                    max_col = col + 1
                    count += 1

            return count

        rows, cols = len(mat), len(mat[0]) if mat else 0
        count = 0
        for row in range(rows):
            for col in range(cols):
                count += count_rectangles(row, col)

        return count

    def numSubmat1(self, mat: List[List[int]]) -> int:
        rows, cols = len(mat), len(mat[0]) if mat else 0
        sizes = [[(0, 0)] * (cols + 1) for _ in range(rows + 1)]

        for row in range(rows):
            for col in range(cols):
                if mat[row][col] == 1:
                    sizes[row + 1][col + 1] = (
                        min(sizes[row][col + 1][0], sizes[row][col][0]) + 1,
                        min(sizes[row + 1][col][1], sizes[row][col][1]) + 1,
                    )

        print(sizes)
        return 0


class Solution:
    def numSubmat(self, mat: List[List[int]]) -> int:
        def oneDim(mat):
            res = 0
            length = 0
            for el in mat:
                if el == 0:
                    length = 0
                else:
                    length += 1
                res += length
            return res
        
        res = 0
        M = len(mat)
        N = len(mat[0])
        for top in range(M):
            h = [1] * N
            for bot in range(top, M):
                for i in range(N):
                    h[i] *= mat[bot][i]
                res += oneDim(h)

        return res

class Solution:
    #Version 1: DP
    #left[i][j] is the longest 1 on the right hand side ending at mat[i][j]
    #up[i][j] is the longest 1 above mat[i][j]
    #TC: O(mnn), SC: O(mn)
    '''
    def numSubmat(self, mat: List[List[int]]) -> int:
        m = len(mat)
        n = len(mat[0])
        left = [[0]*n for _ in range(m)]
        up = [[0]*n for _ in range(m)]
        
        for k in range(m):
            count = 0
            for v in range(n):
                if mat[k][v] == 1:
                    count += 1
                else:
                    count = 0
                left[k][v] = count
                    
        for v in range(n):
            count = 0
            for k in range(m):
                if mat[k][v] == 1:
                    count += 1
                else:
                    count = 0
                up[k][v] = count
            
        ans = 0
        for k in range(m):
            for v in range(n):
                if mat[k][v] == 1:
                    current = up[k][v]
                    for j in range(left[k][v]):
                        current = min(current, up[k][v-j])
                        ans += current
                    #print(k, v, ans, left[k][v], right[k][v], up[k][v], down[k][v])
        return ans
    '''
    
    #Version 2: Stack and dp
    #Consider the histogram in the first m rows
    #dp[k] stores the the number of submatrices using mat[m][k] as the right bottom
    #We can use stack to consider the case, once we found there is a index h[i] <= h[v], the result will be dp[v] = dp[i] + (v-i)*h[v]
    #TC: O(mn), SC: O(n)
    def numSubmat(self, mat: List[List[int]]) -> int:
        m = len(mat)
        n = len(mat[0])
        ans = 0
        h = [0]*n
        for k in range(m):
            for v in range(n):
                if mat[k][v] == 1:
                    h[v] += 1
                else:
                    h[v] = 0

            dp = [0]*n
            # stack = []
            # for v in range(n):
            #     while stack and h[stack[-1]] >= h[v]:
            #         stack.pop()
            #     if not stack:
            #         dp[v] = h[v] * (v+1)
            #     else:
            #         dp[v] = dp[stack[-1]] + (v - stack[-1])*h[v]
            #     stack.append(v)
            #     ans += dp[v]
            dp = [0]*(n+1)
            stack = [[-1, 0]]
            for v in range(n):
                while stack and stack[-1][0] >= h[v]:
                    stack.pop()
                dp[v+1] = dp[stack[-1][1]] + (v + 1 - stack[-1][1])*h[v]
                stack.append([h[v], v+1])
                ans += dp[v+1]
            #print(k, h, dp)
        return ans
    


\"\"\"
google onsite 
二维矩阵包含0和1。问由0组成的sub rectangle有多少个，这个是面经题

我是这样想的不知道对不对，考虑以(i, j)为右下角的最大正方形边长，这个就是lc 221。然后如果以(i, j)为右下角的最大正方形边长是a，则以它为右下角的正方形数目是a，所以把这些加起来就好
因此用以下 dp方法

dp[i][j] 以(i, j)为右下顶点的最大全1矩阵的边长. 也表示 以（i,j）为右下角正方形数量
答案为 sum(dp[i][j])
\"\"\"

\"\"\"
Google onsite
给一个由0，1组成的数组，算子数组全是0的个数。 e.g.[0,0,1,0] 返回4
follow up: 输入是二维矩阵，算子矩阵全是0的个数
\"\"\"

\"\"\"

固定上下边界，找到以当前长度为矩形高的 矩形数量，最后得到总数量

fix up boundary and bottom boundary then find all submatrix with this height 
for how to get all submatrix with this height, we build a array, idx is col idex, val is 1 if all the cells between up and bottom are one, otherwise zero 
than we convert this 2d problem to 1d, we just need to calculate how many rec with all ones in it in this array 

Note: the array h[k] == 1 means all values in column k from row \"up\" to \"down\" are 1 (that's why we use &). So overall, the idea is to \"compress\" the 2D array to the 1D array, and apply 1D array method on it, while trying all heights up to down.


Time O(M * N * M)
Space O(M * N )
\"\"\"
class Solution:
    def numSubmat(self, mat: List[List[int]]) -> int:
        if not mat or not mat[0]:
            return 0 
        n = len(mat)
        m = len(mat[0])
        count = 0
        # enumerate top and bottom boundary  
        for top in range(n):
            arr = [1] * m
            for bottom in range(top, n):
                # convert 2d to 1d array 
                for col in range(m):
                    arr[col] &= mat[bottom][col]
                # get all count of submatrices whose height = bottome - top
                count += self.get_arr_ones_count(arr)
        return count 
    # use curr num as the right boundary of the rectangle 
    def get_arr_ones_count(self, arr):
        res = 0
        count = 0
        for num in arr:
            if num == 0:
                count = 0
            else:
                count += 1 
                res += count 
        return res 
# [[1,0,1],
#  [1,1,0],
#  [1,1,0]]
# arr = [1,0,1], top=0,bottom=0, count = 2
# arr = [2,1,1], top=0,bottom=1, count = 2



class Solution:
    def numSubmat(self, mat: List[List[int]]) -> int:
        # https://www.youtube.com/watch?v=EqzTpLSYK6g
        # O(m ^ 2 * n); Space: O(mn)
        # focus on bottom left matrix, look left and look up
        # 0 0 0 0      0 0 0 0
        # 0 1 1 0  ->  0 1 2 0
        # 0 0 1 0      0 0 1 0
        if not mat:
            return 0
        
        m, n = len(mat), len(mat[0])
        
        dp = [[0] * (n + 1) for _ in range(m + 1)]
        
        res = 0
        for i in range(1, m + 1):
            for j in range(1, n + 1):
                if mat[i - 1][j - 1]:
                    dp[i][j] = dp[i][j - 1] + 1 # look left
                    res += dp[i][j]
                    # look above
                    min_ones = dp[i][j]
                    for k in range(i - 1, -1, -1):
                        min_ones = min(min_ones, dp[k][j])
                        res += min_ones
        return res

class Solution:
    def numSubmat(self, mat: List[List[int]]) -> int:
        counter = 0

        rows = len(mat)

        if rows > 0:
            columns = len(mat[0])

            for i in range(rows):
                for j in range(columns):

                    max_width = 0
                    max_height = 0

                    if mat[i][j] == 1:
                        counter += 1
                        max_width += 1
                        max_height += 1

                        for k in range(j + 1, columns):
                            if mat[i][k] == 1:
                                counter += 1
                                max_width += 1
                            else:
                                break

                        for l in range(i + 1, rows):
                            if mat[l][j] == 1:
                                counter += 1
                                max_height += 1
                                m_w = 1

                                for m in range(j + 1, columns):
                                    if mat[l][m] == 1 and m_w < max_width:
                                        counter += 1
                                        m_w += 1
                                    else:
                                        max_width = min(max_width, m_w)
                                        break
                            else:
                                break
                    else:
                        continue

        return counter


class Solution:
    def numSubmat(self, mat: List[List[int]]) -> int:
        
        info=[[[] for i in range(len(mat[0]))]for j in range(len(mat))]
        
        result=0
        for i in range(len(mat)):
            for j in range(len(mat[0])):
                if i==0 and j==0:
                    info[i][j].append(mat[i][j])
                    result+=mat[i][j]
                elif i==0 and j!=0:
                    if mat[i][j]==1:
                        info[i][j].append(info[i][j-1][0]+1)
                        result+=info[i][j][0]
                    else:
                        info[i][j].append(0)
                elif j==0 and i!=0:
                    if mat[i][j]==1:
                        info[i][j].append(1)
                        if mat[i-1][j]==1:
                            info[i][j]+=info[i-1][j]
                        result+=sum(info[i][j])  
                    else:
                        info[i][j].append(0)
                else:
                    if mat[i][j]==1:
                        info[i][j].append(info[i][j-1][0]+1)
                        if mat[i-1][j]==1:
                            for index in range(len(info[i-1][j])):
                                if index+1 <len(info[i][j-1]):
                                    info[i][j].append(min(info[i][j-1][index+1]+1,info[i-1][j][index]))
                                else:
                                    info[i][j].append(1)
                        result+=sum(info[i][j])      
                    else:
                        info[i][j].append(0)
        
        return result
                    
                


class Solution:
    def numSubmat(self, mat: List[List[int]]) -> int:
        if not mat:
            return 0
        
        m, n = len(mat), len(mat[0])
        
        dp = [[0] * (n + 1) for _ in range(m + 1)]
        
        res = 0
        for i in range(1, m + 1):
            for j in range(1, n + 1):
                if mat[i - 1][j - 1]:
                    dp[i][j] = dp[i][j - 1] + 1
                    res += dp[i][j]
                    min_ones = dp[i][j]
                    for k in range(i - 1, -1, -1):
                        min_ones = min(min_ones, dp[k][j])
                        res += min_ones
        return res

class Solution:
    def numSubmat(self, mat: List[List[int]]) -> int:
        rows = len(mat)
        cols = len(mat[0])
        print(\"rows = {}; cols = {}\".format(rows, cols))
        
        cnt = 0
        
        for tl_row in range(0, rows):
            for tl_col in range(0, cols):
                # May be \"retracted\" as we go along:
                max_width = cols - tl_col
                
                for height in range(1, rows - tl_row + 1):
                    for width in range(1, max_width + 1):
                        cell = mat[tl_row + height - 1][tl_col + width - 1]
                        if cell == 1:
                            cnt += 1
                            continue
                        else:
                            max_width = width - 1
                            break
                            
                    if max_width == 0:
                        break

        return cnt                        
        

class Solution:
    def numSubmat(self, mat: List[List[int]]) -> int:
        r = len(mat)
        c = len(mat[0])
        res = 0
        for up in range(r):
            ans = [1] * c
            for down in range(up, r):
                for j in range(c):
                    ans[j] = ans[j] & mat[down][j]
                res += self.cal(ans)
        return res
    
    def cal(self, ans):
        res = 0
        cur = 0
        n = len(ans)
        for i in range(n):
            if ans[i] == 0:
                cur = 0
            else:
                cur += 1
                res += cur
        return res

class Solution:
    def numSubmat(self, mat: List[List[int]]) -> int:
        
        n=len(mat)
        m=len(mat[0])

        counts=[[0]*m for j in range(n)]
        
        for i in range(n):
            for j in range(m-1, -1, -1):
                if mat[i][j]==1:
                    counts[i][j]+=1+(counts[i][j+1] if j+1<m else 0)
        res=0            
        for i in range(n):
            for j in range(m):
                if mat[i][j]==1:
                    mins=float('inf')
                    for k in range(i, n):
                        mins=min(mins, counts[k][j])
                        res+=mins
                        
        return res

class Solution:
    def numSubmat2(self, mat: List[List[int]]) -> int:
        \"\"\"O(m^2*n)\"\"\"
        def calc(arr):
            res = 0
            leng = 0
            for i in range(len(arr)):
                leng = 0 if arr[i] == 0 else leng + 1
                res += leng
            return res
        m, n = len(mat), len(mat[0])
        res = 0
        for i in range(m):
            arr = [1] * n
            for j in range(i, m):
                for k in range(n):
                    arr[k] &= mat[j][k]
                res += calc(arr)
        return res
    
    def numSubmat(self, mat: List[List[int]]) -> int:
        \"\"\"O(m*n^2)\"\"\"
        def calc(arr):
            res = 0
            leng = 0
            for i in range(len(arr)):
                leng = 0 if arr[i] == 0 else leng + 1
                res += leng
            return res
        def calc2(arr):
            res = 0
            for c, g in itertools.groupby(arr):
                if c == 1:
                    n = len(list(g))
                    res += n * (n + 1)//2
            return res
        m, n = len(mat), len(mat[0])
        res = 0
        for i in range(n):
            arr = [1] * m
            for j in range(i, n):
                for k in range(m):
                    arr[k] &= mat[k][j]
                res += calc2(arr)
        return res

class Solution:
    def numSubmat(self, mat: List[List[int]]) -> int:
        a = mat
        m, n = len(a), len(a[0])
        def hist(h):
            ret = [0] * n
            s = []
            for i, x in enumerate(h):
                while s and h[s[-1]] >= x:
                    s.pop()
                if s:
                    j = s[-1]
                    ret[i] = ret[j] + (i - j) * x
                else:
                    ret[i] = (i + 1) * x
                s.append(i)
            return sum(ret)
        h = [0] * n
        ans = 0
        for row in a:
            for j in range(n):
                h[j] = row[j] + h[j] if row[j] else 0
            ans += hist(h)
        return ans


class Solution:
    def numSubmat(self, mat: List[List[int]]) -> int:
        #refer https://www.youtube.com/watch?v=8miqwSN3EFo&ab_channel=HappyCoding
        m, n = len(mat), len(mat[0])
        
        one_counts = [[0] * n for _ in range(m)]
        
        for i in range(m):
            for j in range(n - 1, -1, -1):
                if mat[i][j] == 1:
                    if j < n - 1:
                        one_counts[i][j] += 1 + one_counts[i][j + 1]
                    else:
                        one_counts[i][j] = 1
        
        ans = 0
        for i in range(m):
            for j in range(n):
                if mat[i][j] != 1:
                    continue
                min_width = sys.maxsize
                for k in range(i, m):
                    min_width = min(min_width, one_counts[k][j])
                    ans += min_width
        
        return ans
        


class Solution:
    def numSubmat(self, mat: List[List[int]]) -> int:
                    
        def helper(arr):
            count = 0
            curr = 0
            
            for item in arr:
                
                if item != 1:
                    curr = 0
                else:
                    curr += 1
                
                count += curr

            return count
        
        result = 0
        for x1 in range(len(mat)):
            
            zeros = [1 for x in range(len(mat[0]))]
            
            for x2 in range(x1, len(mat)):
                
                for col in range(len(mat[0])):
                    
                    zeros[col] &= mat[x2][col]
                
                result += helper(zeros)
        
        return result

class Solution:
    def numSubmat(self, mat: List[List[int]]) -> int:
        # O(m ^ 2 * n); Space: O(mn)
        # focus on bottom left matrix, look left and look up
        # 0 0 0 0      0 0 0 0
        # 0 1 1 0  ->  0 1 2 0
        # 0 0 1 0      0 0 1 0
        if not mat:
            return 0
        
        m, n = len(mat), len(mat[0])
        
        dp = [[0] * (n + 1) for _ in range(m + 1)]
        
        res = 0
        for i in range(1, m + 1):
            for j in range(1, n + 1):
                if mat[i - 1][j - 1]:
                    dp[i][j] = dp[i][j - 1] + 1 # look left
                    res += dp[i][j]
                    # look above
                    min_ones = dp[i][j]
                    for k in range(i - 1, -1, -1):
                        min_ones = min(min_ones, dp[k][j])
                        res += min_ones
        return res

class Solution:
    def numSubmat(self, mat: List[List[int]]) -> int:
        if not mat:
            return 0
        
        m, n = len(mat), len(mat[0])
        
        dp = [[0] * (n + 1) for _ in range(m + 1)]
        
        res = 0
        for i in range(1, m + 1):
            for j in range(1, n + 1):
                if mat[i - 1][j - 1]:
                    dp[i][j] = dp[i][j - 1] + 1 # walk left
                    res += dp[i][j]
                    # walk above
                    min_ones = dp[i][j]
                    for k in range(i - 1, -1, -1):
                        min_ones = min(min_ones, dp[k][j])
                        res += min_ones
        return res

class Solution:
    def numSubmat(self, mat: List[List[int]]) -> int:
        rows = len(mat)+1
        cols = len(mat[0])+1
        dp = [[0 for x in range(cols)] for y in range(rows)]
        for i in range(1, rows):
            dp[i][0] = 0
        for j in range(1, cols):
            dp[0][j] = 0
        
       
        res = 0
        #left most
        for i in range(1, rows):
            for j in range(1, cols):
                if mat[i-1][j-1] == 1:
                    dp[i][j] = dp[i][j-1] + 1
                    res += dp[i][j]
                    min_ones = dp[i][j]
                    #upper most
                    for k in range(i-1, -1, -1):
                        min_ones = min(dp[k][j], min_ones)
                        res += min_ones
        return res

class Solution:
    def numSubmat(self, mat: List[List[int]]) -> int:
        dp = [[0] * (len(mat[0]) + 1) for _ in range(len(mat) + 1)]
        res = 0
        for i in range(1, len(mat) + 1):
            for j in range(1, len(mat[0]) + 1):
                if mat[i - 1][j - 1] == 1:
                    dp[i][j] = 1 + dp[i][j - 1]
                    res += dp[i][j]
                    
                    minRec = dp[i][j]
                    for k in range(i - 1, -1, -1):
                        minRec = min(minRec, dp[k][j])
                        res += minRec
        return res


class Solution:

    def numSubmat(self, mat: List[List[int]]) -> int:
        res = 0
        m = len(mat)
        n = len(mat[0])
        data = [[0 for _ in range(n)] for _ in range(m)] # [i, j] stores consecutive number of 1s from the cell upwards
        for row in range(m): # row
            for col in range(n): # col
                if not mat[row][col]:
                    continue
                data[row][col] = 1 if row == 0 else data[row - 1][col] + 1
                smallest = data[row][col]
                res += smallest
                for j in range(col - 1, -1, -1):
                    smallest = min(smallest, data[row][j])
                    res += smallest
        return res

    
    def numSubmat_v1(self, mat: List[List[int]]) -> int:
        \"\"\"My O(n^4) algorithm
        \"\"\"
        res = 0
        m = len(mat)
        n = len(mat[0])
        data = [[set() for _ in range(n)] for _ in range(m)] # [i, j] stores valid rectangle sizes represented by longth & width
        for row in range(m): # row
            for col in range(n): # col
                if not mat[row][col]:
                    continue
                data[row][col].add((1,1))
                res += 1
                if col > 0:
                    for e in data[row][col - 1]:  # look at all rectangles of the left cell
                        if e[1] == 1:
                            data[row][col].add((e[0] + 1, 1))
                            res += 1
                        elif row > 0 and (1, e[1] - 1) in data[row - 1][col]:
                            data[row][col].add((e[0] + 1, e[1]))
                            res += 1
                if row > 0:
                    for e in data[row - 1][col]:
                        if e[0] == 1:
                            data[row][col].add((1, e[1] + 1))
                            res += 1
        return res
                
                

class Solution:
    def numSubmat(self, mat: List[List[int]]) -> int:
        # similar to 1277
        # but we only look left and look up
        # then take min
        count = 0
        for i in range(len(mat)):
            for j in range(len(mat[0])):
                if mat[i][j]==1:
                    # look left
                    mat[i][j] = mat[i][j-1]+1 if j>0 else 1
                    count += mat[i][j]
                    # look up
                    # need to go up to top
                    # to count all possible recs
                    min_ones = mat[i][j]
                    for k in range(i-1, -1, -1):
                        min_ones = min(min_ones, mat[k][j])
                        count += min_ones
        return count

class Solution:   
    def numSubmat(self, mat: List[List[int]]) -> int:    
        M=len(mat)
        N=len(mat[0])
        histogram=[[0 for _ in range(N)] for _ in range(M)] 
        dp=[[0 for _ in range(N)] for _ in range(M)] 
        ## monoI stack (index) for storing histogram 
        stack=[[] for _ in range(N)] 
        
        for m in range(M):
            for n in range(N):
                if n==0:
                    histogram[m][n]=mat[m][n]
                else:
                    histogram[m][n]=histogram[m][n-1]+1 if mat[m][n]==1 else 0
        
        res=0  
        for bottom in range(M):
            for right in range(N):
                while stack[right] and histogram[stack[right][-1]][right]>histogram[bottom][right]:
                    stack[right].pop()
                if stack[right]:
                    dp[bottom][right]=dp[stack[right][-1]][right]\\
                                        +histogram[bottom][right]*(bottom-stack[right][-1])       
                else:
                    dp[bottom][right]=histogram[bottom][right]*(bottom+1)
                    
                stack[right].append(bottom)
                res+=dp[bottom][right]  
                
        return res

    
#-----------|||||||||||||||||||||||||||||||||||||||||||||||||-------------------#   

#     ## O(M*N*M)
#     def numSubmat(self, mat: List[List[int]]) -> int:
#         M=len(mat)
#         N=len(mat[0])
        
#         # num of consecutive ones to the left of (x,y) in the same row
#         histogram=[[0 for _ in range(N)] for _ in range(M)] 

#         for m in range(M):
#             for n in range(N):
#                 if n==0:
#                     histogram[m][n]=mat[m][n]
#                 else:
#                     histogram[m][n]=histogram[m][n-1]+1 if mat[m][n]==1 else 0
#         res=0          
#         for bottom in range(M):
#             for right in range(N):
#                 Min=histogram[bottom][right]
#                 for upper in range(bottom+1)[::-1]:      
#                     Min=min(Min,histogram[upper][right])
#                     if Min==0:
#                         break
#                     res+=Min
                    
#         return res

#-----------|||||||||||||||||||||||||||||||||||||||||||||||||-------------------#                    
        
#     ## Brute Force w/ Pruning O(N^2*M^2)
#     def numSubmat(self, mat: List[List[int]]) -> int:
#         M=len(mat)
#         N=len(mat[0])
#         res=0       
        
#         for top in range(M):
#             for left in range(N):
#                 bound=N ## to bound the right pointer
#                 for bottom in range(top,M):                    
#                     right=left
#                     while right<bound:
#                         if mat[bottom][right]==1:
#                             res+=1
#                             right+=1
#                         else:
#                             bound=right
#                             break
#         return res                  
                        
                        
                    
                
        

class Solution:
    def numSubmat(self, mat: List[List[int]]) -> int:
        m, n = len(mat), len(mat[0])
        
        def count_sub(i, j):
            max_c = n
            count = 0 
            for r in range(i, m):
                for c in range(j, max_c):
                    if mat[r][c] == 1:
                        count += 1
                    else:
                        max_c = c
                        break
            return count
        
        
        ans = 0
        for i in range(m):
            for j in range(n):
                if mat[i][j]:
                    ans += count_sub(i, j)
        return ans

class Solution:
    def numSubmat(self, mat: List[List[int]]) -> int:

        def countOneRow(A):
            res, length = 0, 0
            for a in A:
                length =  0 if a == 0 else length + 1
                res += length
            return res

        res, M, N = 0, len(mat), len(mat[0])
        
        for up in range(M):
            onesCol = [1] * N
            for down in range(up, M):
                for i in range(N):
                    onesCol[i] &= mat[down][i]
                res += countOneRow(onesCol)
        return res
                
            


class Solution:
    def numSubmat(self, mat: List[List[int]]) -> int:
        rows,cols = len(mat),len(mat[0])  
        
        def one_d_sum(h):
            ans = 0
            length = 0
            for i in range(len(h)):
                if h[i] == 1:
                    length += 1
                else:
                    length = 0
                ans += length
            return ans
        
        
        ans = 0
        for top_row in range(rows):
            h = [1] * cols
            for bottom_row in range(top_row,rows):
                for k in range(cols):
                    h[k] = h[k] & mat[bottom_row][k]
                ans += one_d_sum(h)
        return ans
        
        
        
        
        
        
        
        
        
        
        










#         h, w = len(mat), len(mat[0])
        
#         # dp table:
#         # record the maximum length of continuous 1 from left-most column to specified column
#         dp_acc_of_1 = [ [ 0 for _ in range(w)] for _ in range(h) ]
        
#         for y in range(h):
#             for x in range(w):
                
#                 if x == 0:
#                     # left-most column
#                     dp_acc_of_1[y][x] = mat[y][x]
                    
#                 else:
#                     # not left-most column
#                     if mat[y][x] == 1:
#                         dp_acc_of_1[y][x] = dp_acc_of_1[y][x-1] + 1
                        

#         counter_of_rectangle = 0
        
#         for y in range(h):
#             for x in range(w):
                
#                 # update the total number of rectangle, whose bottom right anchor point is [y][x]
                
#                 minimum_width = dp_acc_of_1[y][x]
                
#                 for h_idx in range(y, -1, -1):
#                     minimum_width = min(minimum_width, dp_acc_of_1[h_idx][x])
#                     counter_of_rectangle += minimum_width
                    
#                     if minimum_width == 0:
#                         # no chance to make rectangle
#                         break
                        
#         return counter_of_rectangle


class Solution:
    def numSubmat(self, mat: List[List[int]]) -> int:
        
        row = len(mat)
        col = len(mat[0])
        res = 0

        def calculate1dArray(arr):
            ans = 0
            pre = 0
            for i, a in enumerate(arr):
                if a == 1:
                    pre += 1
                    ans += pre
                else:
                    pre = 0
            return ans 
        
        for a in range(row):
            arr = [1] * col
            for b in range(a, row):
                for c in range(col):
                    arr[c] &= mat[b][c] 
                res += calculate1dArray(arr)
        return res 


class Solution:
    def numSubmat(self, mat: List[List[int]]) -> int:
        
        # 生成直方图histogram
        def countOneRow(arr):
            res = 0
            l = 0
            for i in range(len(arr)):
                if arr[i] == 0:
                    l = 0
                else: l = l + 1
                res += l # 以当前为最右，可以形成l个矩形
            return res
        
        rows = len(mat)
        cols = len(mat[0])
        res = 0
        for top in range(rows):
            h = [1] * cols
            l = 0
            for bottom in range(top, rows):
                for c in range(cols):
                    # 每一行都跟top来merge，因为中间必须所有格都是1，才能形成一个矩形
                    h[c] &= mat[bottom][c]
                    l |= h[c]
                res += countOneRow(h)
                if not any(h): break
        return res

class Solution:
    def numSubmat(self, mat: List[List[int]]) -> int:
        
        res = 0
        
        m, n = len(mat), len(mat[0])
        
        dp = [[0] * n for i in range(m)]
        
        for i in range(m):
            
            prev = 0
            
            for j in range(n - 1, -1, -1):
                
                if mat[i][j] == 1:
                    
                    dp[i][j] = prev + 1
                    
                    prev = dp[i][j]
                    
                else:
                    
                    prev = 0
                    
        for i in range(m):
            
            for j in range(n):
                
                if mat[i][j] == 1:
                    
                    min_right = dp[i][j]
                    
                    for k in range(i, m):
                        
                        min_right = min(min_right, dp[k][j])
                        
                        res += min_right
                        
        return res


class Solution:
    def numSubmat(self, mat: List[List[int]]) -> int:
        m, n = len(mat), len(mat[0])
        
        def count_sub(i, j):
            max_c = n
            count = 0 
            for r in range(i, m):
                for c in range(j, max_c):
                    if mat[r][c] == 1:
                        count += 1
                    else:
                        max_c = c
                        break
                if not max_c:
                    break
            return count
        
        
        ans = 0
        for i in range(m):
            for j in range(n):
                if mat[i][j]:
                    ans += count_sub(i, j)
        return ans

class Solution:
    def numSubmat(self, mat: List[List[int]]) -> int:
        M=len(mat)
        N=len(mat[0])
        
        mark=[[0 for _ in range(N)] for _ in range(M)]
        
        for m in range(M):
            for n in range(N):
                if n==0:
                    mark[m][n]=mat[m][n]
                else:
                    mark[m][n]=mark[m][n-1]+1 if mat[m][n]==1 else 0
        res=0          
        for bottom in range(M):
            for right in range(N):
                Min=mark[bottom][right]
                for upper in range(bottom+1)[::-1]:      
                    Min=min(Min,mark[upper][right])
                    res+=Min
                    
        return res
                    
        
#     ## Brute Force w/ Pruning O(N^2*M^2)
#     def numSubmat(self, mat: List[List[int]]) -> int:
#         M=len(mat)
#         N=len(mat[0])
#         res=0       
        
#         for top in range(M):
#             for left in range(N):
#                 bound=N ## to bound the right pointer
#                 for bottom in range(top,M):                    
#                     right=left
#                     while right<bound:
#                         if mat[bottom][right]==1:
#                             res+=1
#                             right+=1
#                         else:
#                             bound=right
#                             break
#         return res                  
                        
                        
                    
                


class Solution:
    def countSubMat(self,rowmat:List[int])->int:
        count=rowmat[0]
        for i in range(1,len(rowmat)):
            rowmat[i]=0 if rowmat[i]==0 else (rowmat[i-1]+rowmat[i])
            count+=rowmat[i]
        
        # length=0
        # count=0
        # for i in range(len(rowmat)):
        #     length=0 if rowmat[i]==0 else (length+1)
        #     count+=length
        return count
    
    def numSubmat(self, mat: List[List[int]]) -> int:
        count=0
        
        for m in range(len(mat)):
            
            h=[1 for _ in range(len(mat[0]))]
            for down in range(m,len(mat),1):
                for n in range(len(mat[0])):
                    h[n]=h[n]and mat[down][n]
                
                count+=self.countSubMat(h)
                
        return count
        
        #[[1,0,1],[1,1,0],[1,1,0]]
#     def numSubmat(self, mat: List[List[int]]) -> int:
#         count=0
        
#         #filter size
#         for i in range(len(mat)):
#             for j in range(len(mat[0])):
                
#                 #for all position
#                 for a in range(len(mat)):
#                     if a+i<len(mat):
#                         for b in range(len(mat[0])):
#                             if b+j<len(mat[0]):
#                                 tmp=0
                                
#                                 #for position inside filter
#                                 for c in range(a,a+i+1,1):
#                                     for d in range(b,b+j+1,1):
#                                         tmp+=mat[c][d]
                                        
#                                 if tmp==((i+1)*(j+1)):
#                                     count+=1
#         return count
#            #[[1,0,1],[1,1,0],[1,1,0]]             
                        
                        


class Solution:
    def numSubmat(self, mat: List[List[int]]) -> int:
        m, n = len(mat), len(mat[0])
        left = [[0 for j in range(n+1)] for i in range(m+1)]
        for i in range(1, len(left)):
            for j in range(1, len(left[0])):
                if mat[i-1][j-1] == 1:
                    left[i][j] = left[i][j-1] + 1
        res = 0
        for i in range(len(mat)):
            for j in range(len(mat[0])):
                minlen = float('inf')
                for k in range(i, -1, -1):
                    minlen = min(minlen, left[k+1][j+1])
                    res += minlen
        return res


class Solution:
    def numSubmat(self, mat: List[List[int]]) -> int:
        # 这道题是问有多少个submatrices有all ones
        # 和84Largest Rectangle in Histogram很像
         
        # 解法1 - 枚举右下角
        m, n = len(mat), len(mat[0])
        left_ones = [[0] * n for _ in range(m)]
        for i in range(m):
            for j in range(n):
                if mat[i][j] == 0:
                    left_ones[i][j] = 0
                else:
                    left_ones[i][j] = 1
                    if j > 0:
                        left_ones[i][j] += left_ones[i][j - 1]
        
#         res = 0
#         for i in range(m):
#             for j in range(n):
#                 curr_left_ones = left_ones[i][j]
#                 for k in range(i, -1, -1):
#                     curr_left_ones = min(curr_left_ones, left_ones[k][j])
#                     res += curr_left_ones
        
#         return res


        res = 0
        for j in range(n):
            total = 0
            stack = []
            for i in range(m):
                height = 1
                total += left_ones[i][j]
                while stack and stack[-1][0] > left_ones[i][j]:
                    # 弹出的时候要减去多于的答案
                    total -= stack[-1][1] * (stack[-1][0] - left_ones[i][j])
                    height += stack[-1][1]
                    stack.pop()
                res += total
                stack.append((left_ones[i][j], height))

        return res



class Solution:
    def numSubmat(self, mat: List[List[int]]) -> int:
        if not mat or not mat[0]:
            return 0
        m, n = len(mat), len(mat[0])
        hts = [0]*n
        ans = 0
        for i in range(m):
            for j in range(n):
                hts[j] = hts[j]+1 if mat[i][j] else 0
            for j in range(n):
                minh = m
                for k in range(j, n):
                    minh = min(minh, hts[k])
                    ans += minh
        return ans


class Solution:
    def numSubmat(self, mat: List[List[int]]) -> int:
        res = 0
        
        for i in range(len(mat)):
            row = [ 1 for _ in range(len(mat[0])) ]
            for j in range(i, len(mat)):
                for k in range(len(mat[0])):
                    row[k] &= mat[j][k]
                res += self.countRow(row)
                
        return res
    
    def countRow(self, row: List[int]) -> int:
        res = length = 0
        
        for i, val in enumerate(row):
            length = 0 if val == 0 else length + 1
            res += length
        
        return res

class Solution:
    def numSubmat(self, mat: List[List[int]]) -> int:
        
        R = len(mat)
        C = len(mat[0])
        dp = [[None for i in range(C)] for j in range(R)]
        
        for i in range(R):
            count = 0
            for j in range(C-1,-1, -1):
                if mat[i][j] == 1:
                    count += 1
                else:
                    count = 0
                dp[i][j] = count
        
        result = 0
        for i in range(R):
            for j in range(C):
                mn = float(\"inf\")
                for k in range(i, R):
                    mn = min(mn, dp[k][j])
                    result += mn
        
        return result


class Solution:
    def numSubmat(self, mat) -> int:
        m, n = len(mat), len(mat[0])
        res = 0
        for up in range(m):
            h = [1]*n
            for down in range(up, m):
                for k in range(n):
                    h[k] &= mat[down][k]
                res += self.countOneRow(h)
        return res

    def countOneRow(self, arr):
        res, length = 0, 0
        for i in range(len(arr)):
            length = 0 if arr[i]==0 else length+1
            res += length
        return res


class Solution:
    def numSubmat(self, mat: List[List[int]]) -> int:
        m,n = len(mat),len(mat[0])     
        
        dp = [[None for i in range(n)]for j in range(m)]
        
        for i in range(m):
            count=0
            
            #It will find consecutive ones horizontally
            for j in range(n-1,-1,-1):
                if mat[i][j]:
                    count+=1
                else:
                    count=0
                dp[i][j]=count
                
                
        ans = 0
        
        for i in range(m):
            for j in range(n):
                
                #We will take min in that column
                mn = float('inf')
                for k in range(i,m):
                    mn = min(mn,dp[k][j])
                    ans+=mn
                print()
                    
        return ans

class Solution:
    def numSubmat(self, mat: List[List[int]]) -> int:
        if not mat:return 0
        m,n = len(mat),len(mat[0])
        res = 0
        #RLE - Run length encoding
        for i in range(m):
            for j in range(n):
                if  j:
                    if mat[i][j]:
                        mat[i][j] = mat[i][j-1] + 1
                        
        #Now,calculate all the rectangular submatrices from the RLE
        print(mat)
        for i in range(m):    
            for j in range(n):
                # (i,j) :top right of matrix
                ans = mat[i][j]
                for k in range(i,m):#bottom-right
                    ans = min(ans,mat[k][j])
                    res+= ans
    
        return res

class Solution:
    def numSubmat(self, mat: List[List[int]]) -> int:
        if not mat:return 0
        m,n = len(mat),len(mat[0])
        res = 0
        #RLE - Run length encoding
        for i in range(m):
            for j in range(n):
                if  j:
                    if mat[i][j]:
                        mat[i][j] = mat[i][j-1] + 1
                        
        #Now,calculate all the rectangular submatrices from the RLE
        print(mat)
        for i in range(m):    
            for j in range(n):
                # (i,j) :top right of matrix
                ans = mat[i][j]
                for k in range(i,m):#bottom-right
                    ans = min(ans,mat[k][j])
                    res+= ans
    
        return res


class Solution:
    def numSubmat(self, mat: List[List[int]]) -> int:
        n=len(mat)
        m=len(mat[0])
        
        for i in range(n):
            for j in range(m-2,-1,-1):
                
                if mat[i][j]:
                    mat[i][j]+=mat[i][j+1]
                    
                    
        ans=0
        
        for i in range(n):
            for j in range(m):
                mini=float(\"inf\")
                for k in range(i,n):
                    mini=min(mini,mat[k][j])
                    
                    ans+=mini
                    
        return ans
                    
        
        
        
        
        

class Solution:
    def numSubmat(self, mat) -> int:

        m, n = len(mat), len(mat[0])
        consective = [0] * m
        res = 0
        for line in range(n):
            for row in range(m):
                if mat[row][line] == 1:
                    consective[row] += 1
                else:
                    consective[row] = 0
            stack = []
            for i in range(m):
                val = consective[i]
                while stack and val <= stack[-1][0]:
                    stack.pop()
                stack.append((val, i))
                for k in range(len(stack)):
                    if k == 0:
                        a, b = stack[k]
                        res += a * (b + 1)
                    else:
                        a, b = stack[k - 1]
                        c, d = stack[k]
                        res += c * (d - b)
        return res

class Solution:
    def numSubmat(self, mat: List[List[int]]) -> int:
        # get potential widths of rectangles, then process downward for all rectangles defined by width
        
        # process widths
        rows, cols = len(mat), len(mat[0])
        for r in range(rows):
            for c in range(1, cols):
                mat[r][c] = 1 + mat[r][c-1] if mat[r][c] else 0
        
        # process downwards for each potential width
        rectangles = 0
        for r in range(rows):
            for c in range(cols):
                width = mat[r][c]
                if width:
                    row = r
                    while row < rows:
                        width = min(width, mat[row][c])
                        rectangles += width
                        row += 1
        
        return rectangles

class Solution:
    def numSubmat(self, mat: List[List[int]]) -> int:
        
        def rectangles_staring_at(i,j):
            res = 0
            max_col = m
            for x in range(i,n):
                for y in range(j,max_col):
                    if mat[x][y] == 1:
                        res+=1
                    else:
                        max_col = y
                        break
            return res
        
        sums = [list(accumulate(row)) for row in mat]
        print(sums)
        ans, n, m = 0, len(mat), len(mat[0])
        for i in range(n):
            for j in range(m):
                ans+=rectangles_staring_at(i,j)
                            
        return ans

class Solution:
    def numSubmat(self, mat: List[List[int]]) -> int:
        n, m = len(mat), len(mat[0])

        for i in range(n):
            for j in range(m-1):
                if mat[i][j+1]:
                    mat[i][j+1] += mat[i][j]

        ans = 0

        for j in range(m):
            for i in range(n):
                add = mat[i][j]
                for k in range(i, n):
                    add = min(add, mat[k][j])
                    ans += add

        return ans

class Solution:
    def numSubmat(self, mat: List[List[int]]) -> int:
        if not mat:return 0
        m,n = len(mat),len(mat[0])
        res = 0
        #RLE - Run length encoding
        for i in range(m):
            for j in range(n):
                if j:
                    if mat[i][j]:
                        mat[i][j] = mat[i][j-1] + 1
                        
        #Now,calculate all the rectangular submatrices from the RLE
        print(mat)
        for i in range(m):    
            for j in range(n):
                # (i,j) :top right of matrix
                ans = mat[i][j]
                for k in range(i,m):#bottom-right
                    ans = min(ans,mat[k][j])
                    res+= ans
    
        return res


class Solution:
    def numSubmat(self, mat: List[List[int]]) -> int:
        n=len(mat)
        m=len(mat[0])
        ar=[]
        for i in range(n):
            a=[]
            for j in range(m):
                a.append(0)
            ar.append(a)
        for i in range(n):
            c=0
            for j in range(m-1,-1,-1):
                if(mat[i][j]==1):
                    c+=1
                else:
                    c=0
                ar[i][j]=c
        ans=0
        for i in range(n):
            for j in range(m):
                import sys
                x=sys.maxsize
                for k in range(i,n):
                    x=min(x,ar[k][j])
                    ans+=x
        return ans
                    


class Solution:
    def numSubmat(self, mat: List[List[int]]) -> int:
        
        R =len(mat)
        C = len(mat[0])
        def sunmat(sr,sc):
            maxc=C
            count=0
            for x in range(sr,R):
                for y in range(sc,maxc):
                    if mat[x][y]==1:
                        count+=1
                    else:
                        maxc=y
                        break
            return count
        res=0
        for x in range(R):
            for y in range(C):
                if mat[x][y]==0:
                    continue
                res+=sunmat(x,y)
        return res
    


class Solution:
    def numSubmat(self, mat: List[List[int]]) -> int:
        
        for i in range(len(mat)):
            for j in range(len(mat[0])):
                if j != 0 and mat[i][j] == 1:
                    mat[i][j] = mat[i][j-1] + 1
                    
        
        res = 0
        for i in range(len(mat)):
            for j in range(len(mat[0])):
                
                ans = mat[i][j]
                for k in range(i,len(mat)):
                    ans = min(ans,mat[k][j])
                    res += ans
                    
        return res
                    


class Solution:
    def numSubmat(self, mat: List[List[int]]) -> int:
        row = len(mat)
        col = len(mat[0])
        
        for j in range(col-2,-1,-1):
            for i in range(row):
                if mat[i][j] == 1:
                    mat[i][j] += mat[i][j+1]
        
        res = 0
        for i in range(row):
            for j in range(col):
                MIN = float(\"inf\")
                for k in range(i, row):
                    MIN = min(MIN, mat[k][j])
                    res += MIN
        return res
        

class Solution:
    def numSubmat(self, mat: List[List[int]]) -> int:
        R, C = len(mat), len(mat[0])
        for r in range(R):
            for c in range(1, C):
                if mat[r][c]: mat[r][c] = mat[r][c-1] + 1
        ans = 0
        for r in range(R):
            for c in range(C):
                if mat[r][c]:
                    minWidth = mat[r][c]
                    row = r
                    while row < R:
                        minWidth = min(minWidth, mat[row][c])
                        ans += minWidth
                        row += 1 
        return ans




class Solution:
    def numSubmat(self, mat: List[List[int]]) -> int:
        # 这道题是问有多少个submatrices有all ones
        # 和84Largest Rectangle in Histogram很像
         
        # 解法1 - 枚举右下角
        m, n = len(mat), len(mat[0])
        left_ones = [[0] * n for _ in range(m)]
        for i in range(m):
            for j in range(n):
                if mat[i][j] == 0:
                    left_ones[i][j] = 0
                else:
                    left_ones[i][j] = 1
                    if j > 0:
                        left_ones[i][j] += left_ones[i][j - 1]
        
#         res = 0
#         for i in range(m):
#             for j in range(n):
#                 curr_left_ones = left_ones[i][j]
#                 for k in range(i, -1, -1):
#                     curr_left_ones = min(curr_left_ones, left_ones[k][j])
#                     res += curr_left_ones
        
#         return res


        ans = 0
        for j in range(n):
            Q = list()
            total = 0
            for i in range(m):
                height = 1
                while Q and Q[-1][0] > left_ones[i][j]:
                    # 弹出的时候要减去多于的答案
                    total -= Q[-1][1] * (Q[-1][0] - left_ones[i][j])
                    height += Q[-1][1]
                    Q.pop()
                total += left_ones[i][j]
                ans += total
                Q.append((left_ones[i][j], height))

        return ans



\"\"\"
Algo
In the first step, stack mat row by row to get the \"histogram model\". For example,

mat = [[1,0,1],
       [1,1,0],
       [1,1,0]]
becomes

mat = [[1,0,1],
       [2,1,0],
       [3,2,0]]
In the second step, traverse the stacked matrix row by row. At each position i, j, compute the number of all-1 submatrices like below.

Define a stack to store indices of non-decreasing height, and a variable cnt for the number of all-1 submatrices at given position (i, j). Take the height of row i as an example, say h = mat[i]. At column j, if h[j-1] <= h[j], it is apparent that cnt[j] = cnt[j-1] + h[j], since every case that contributes to cnt[j-1] could be added a new column of 1's from the jth column to contribute to cnt[j].

The tricky part is when h[j-1] > h[j]. In this case, we need to \"hypothetically\" lower h[j-1] to h[j] to get an updated cnt*[j-1] before adding h[j] to get cnt[j]. Suppose that the histogram is like below to reflect 3,3,3,2. To compute cnt[3], we have to adjust cnt[2] to a hypothetical height of 2 by removing top row before adding the new column to get cnt[3]. The specific operation is done using a mono-stack which stores indices of non-decreasing height. Whenever a new height comes in, pop out the heights in the stack that are higher than the new height while removing the quota contributed by the extra height (between poped height and new height).

* * * 
* * * * 
* * * *
\"\"\"
class Solution:
    def numSubmat(self, mat: List[List[int]]) -> int:
        if not mat:return 0
        m,n = len(mat),len(mat[0])
        res = 0
        #RLE - Run length encoding
        for i in range(m):
            for j in range(n):
                if  j:
                    if mat[i][j]:
                        mat[i][j] = mat[i][j-1] + 1
                        
        #Now,calculate all the rectangular submatrices from the RLE
        print(mat)
        for i in range(m):    
            for j in range(n):
                # (i,j) :top right of matrix
                ans = mat[i][j]
                for k in range(i,m):#bottom-right
                    ans = min(ans,mat[k][j])
                    res+= ans
    
        return res

class Solution:
    def numSubmat(self, mat: List[List[int]]) -> int:
        right_ct=[[0]*len(mat[0]) for _ in range(len(mat))]
        for i in range(len(mat)):
            ct=0
            for j in range(len(mat[0])-1,-1,-1):
                if mat[i][j]==1:
                    ct+=1
                else:
                    ct=0
                right_ct[i][j]=ct
        
        res=0
        
        for i in range(len(mat)):
            for j in range(len(mat[0])):
                right_min=float('inf')
                for k in range(i,len(mat)):
                    right_min=min(right_min,right_ct[k][j])
                    res+=right_min
        
        return res

class Solution:
    def numSubmat(self, mat: List[List[int]]) -> int:
        # 这道题是问有多少个submatrices有all ones
        # 和84Largest Rectangle in Histogram很像
         
        # 解法1 - 枚举右下角, 但是要先准备一个row_left_ones的矩阵方便快速查找
        m, n = len(mat), len(mat[0])
        row_left_ones = [[0] * n for _ in range(m)]
        for i in range(m):
            for j in range(n):
                if mat[i][j] == 0:
                    row_left_ones[i][j] = 0
                else:
                    row_left_ones[i][j] = 1
                    if j > 0:
                        row_left_ones[i][j] += row_left_ones[i][j - 1]
        
        res = 0
        for i in range(m):
            for j in range(n):
                curr_row_left_ones = row_left_ones[i][j]
                for k in range(i, -1, -1):
                    curr_row_left_ones = min(curr_row_left_ones, row_left_ones[k][j])
                    res += curr_row_left_ones
        
        return res

        #=================分割线=================#

        # 解法2 - 单调递增栈(从上往下，即遍历行i的顺序)
        res = 0
        for j in range(n):
            total = 0
            # stack里存两个信息：
            # 1. ij位置上的左1数目(height)
            # 2. 当前的宽度(实际上是垂直的高度, 我们相当于横着看)
            stack = []
            for i in range(m):
                total += left_ones[i][j]
                width = 1
                while stack and stack[-1][0] > left_ones[i][j]:
                    # 弹出的时候要减去多余的答案
                    last_ones, last_width = stack.pop()
                    # last_ones - left_ones[i][j] 看成多余的列数（比如多余5列）
                    # 这5列都和当前的右下角(i, j)能构成5个虚假的矩形
                    # 所以要减掉
                    total -= last_width * (last_ones - left_ones[i][j])
                    width += last_width
                res += total
                stack.append((left_ones[i][j], width))

        return res

class Solution:
    def numSubmat(self, mat: List[List[int]]) -> int:
        n = len(mat)
        m = len(mat[0])
        
        ones = [[0] * (m + 1) for _ in range(n)]
        for i in range(n):
            for j in range(m - 1, -1, -1):
                if mat[i][j] == 0:
                    continue
                ones[i][j] += 1 + ones[i][j + 1]
        res = 0
        for i in range(n):
            for j in range(m):
                width = ones[i][j]
                for k in range(i, n):
                    width = min(width, ones[k][j])
                    res += width
        return res


class Solution:
    def numSubmat(self, mat: List[List[int]]) -> int:
        #took help from discussion
        for i in range(len(mat)):
            for j in range(len(mat[0])-2, -1, -1):
                if mat[i][j] > 0:
                    mat[i][j] += mat[i][j+1]
                
        ans = 0       
        for i in range(len(mat)):
            for j in range(len(mat[0])):
                temp = float(\"inf\")
                for k in range(i, len(mat)):
                    temp = min(temp, mat[k][j])
                    ans += temp
                    
        return ans

class Solution:
    def numSubmat(self, mat: List[List[int]]) -> int:
        ar = [[0]*len(mat[0]) for _ in range(len(mat))]
        for i in range(len(mat)):
            c = 0
            for j in range(len(mat[0])):
                if mat[i][j]: c += 1
                else: c = 0
                ar[i][j] = c
        for r in mat:
            print(r)
        print()
        for r in ar:
            print(r)
        print()
        ans = 0
        for i in range(len(mat)):
            for j in range(len(mat[0])):
                x = float('inf')
                for k in range(i, len(mat)):
                    x = min(x, ar[k][j])
                    ans += x
        return ans
        
        # out = mat[0][0]
        # mat[0][0] = [mat[0][0]]*3 # [row,col,diag]
        # for i in range(1, len(mat)):
        #     if mat[i][0]:
        #         row = 1 + mat[i-1][0][0]
        #         mat[i][0] = [row, 1, 1]
        #         out += row
        #     else:
        #         mat[i][0] = [0]*3
        # for r in mat:
        #     print(r)
        # print()
        # for j in range(1, len(mat[0])):
        #     if mat[0][j]:
        #         col = 1 + mat[0][j-1][1]
        #         mat[0][j] = [1, col, 1]
        #         out += col
        #     else:
        #         mat[0][j] = [0]*3
        # for r in mat:
        #     print(r)
        # print()
        # for i in range(1, len(mat)):
        #     for j in range(1, len(mat[0])):
        #         if mat[i][j]:
        #             row, col, diag = 1 + mat[i-1][j][0], 1 + mat[i][j-1][1], 1 + min(mat[i-1][j][0], mat[i][j-1][1], mat[i-1][j-1][2])
        #             mat[i][j] = [row, col, diag]
        #             out += row + col + diag - 2 # -2 to avoid triple counting
        #         else:
        #             mat[i][j] = [0]*3
        # for r in mat:
        #     print(r)
        # return out


class Solution:
    def numSubmat(self, mat: List[List[int]]) -> int:
        def countOneRow(a):
            res = 0
            length = 0
            for el in a:
                if el == 0:
                    length = 0
                else:
                    length += 1

                res += length
            return res
        
        M = len(mat)
        N = len(mat[0])
        res = 0
        for up in range(M):
            h = [1] * N
            for down in range(up, M):
                for k in range(N):
                    h[k] *= mat[down][k]
                print(h)
                res += countOneRow(h)
        return res


class Solution:
    def numSubmat(self, mat: List[List[int]]) -> int:
        m,n = len(mat),len(mat[0])     
        
        dp = [[0 for i in range(n)] for j in range(m)]
        
        for i in range(m):
            count=0
            
            #It will find consecutive ones horizontally
            for j in range(n-1,-1,-1):
                if mat[i][j]:
                    count+=1
                else:
                    count=0
                dp[i][j]=count
                
        ans = 0
        for i in range(m):
            for j in range(n):
                
                mn = float('inf')
                for k in range(i,m):
                    mn = min(mn,dp[k][j])
                    ans+=mn
                    
        return ans


class Solution:
    def numSubmat(self, mat: List[List[int]]) -> int:
        
        r=len(mat)
        c=len(mat[0])
        for i in range(r):
            for j in range(c-2,-1,-1):
                if mat[i][j]!=0:
                    mat[i][j]=mat[i][j+1]+1
        # print(mat)
        count=0
        for i in range(r):
            for j in range(c):
                width=mat[i][j]
                for k in range(i,r):
                    width=min(width,mat[k][j])
                    count+=width
        
        return count
                    


class Solution:
    def numSubmat(self, mat: List[List[int]]) -> int:
        ret = 0
        for i in range(len(mat)):
            for j in range(len(mat[0])):
                maxRight = len(mat[0])
                for h in range(i, len(mat)):
                    for w in range(j, maxRight):
                        if mat[h][w] == 1:
                            ret += 1
                        else:
                            maxRight = w
                            break
        return ret

class Solution:
    def numSubmat(self, mat: List[List[int]]) -> int:
        n_row = len(mat)
        if n_row == 0:
            return 0
        n_col = len(mat[0])
        if n_col == 0:
            return 0
        
        result = 0
        hist = [0] * (n_col + 1)
        for row in range(n_row):
            min_hist_indices = [-1]
            dp = [0] * (n_col + 1)
            for col in range(n_col):
                hist[col] = 0 if mat[row][col] == 0 else hist[col] + 1
                
                while hist[col] < hist[min_hist_indices[-1]]:
                    min_hist_indices.pop()
                
                dp[col] = dp[min_hist_indices[-1]] + hist[col] * (col - min_hist_indices[-1])
                
                min_hist_indices.append(col)
                
            result += sum(dp)
        return result

class Solution:
    def numSubmat(self, mat: List[List[int]]) -> int:
        def num(mat,i,j):
            result = 0
            index_i = i
            
            while index_i<len(mat) and mat[index_i][j] == 1:
                result += 1
                index_i += 1
            index_j = j
            while index_j<len(mat[0]) and mat[i][index_j] == 1:
                result += 1
                index_j += 1
                
            result -= 1
            print(result)
            bound_i = index_i
            bound_j = index_j
            for row in range(i+1,bound_i):
                for col in range(j+1,bound_j):
                    if mat[row][col] == 1:
                        result += 1
                    else:
                        bound_i = row
                        bound_j = col
                        break
                        
            return result
        \"\"\"
        if len(mat) == 0 or len(mat[0]) == 0:
            return 0
        
        result = 0
        for i in range(len(mat)):
            for j in range(len(mat[0])):
                if mat[i][j] == 1:
                    n = num(mat,i,j)
                    print(n)
                    result += n
        return result
        \"\"\"
        
        \"\"\"
        #O(n*n*m)
        row = [[0]*len(mat[0]) for _ in range(len(mat))]
        
        for i in range(len(mat)):
            for j in range(len(mat[0])):
                if mat[i][j] == 1:
                    if j == 0:
                        row[i][j] = 1
                    else:
                        row[i][j] = row[i][j-1] + 1
        result = 0
        for i in range(len(mat)):
            for j in range(len(mat[0])):
                if mat[i][j] == 1:
                    if i == 0:
                        result += row[i][j]
                    else:
                        result += row[i][j]
                        index = i - 1
                        bound = row[i][j]
                        while index>=0:
                            bound = min(bound,row[index][j])
                            if bound == 0:
                                break
                            result += min(row[i][j],bound)
                            index = index - 1
        return result
        \"\"\"
        
        row = [[0]*len(mat[0]) for _ in range(len(mat))]
        
        for i in range(len(mat)):
            for j in range(len(mat[0])):
                if mat[i][j] == 1:
                    if j == 0:
                        row[i][j] = 1
                    else:
                        row[i][j] = row[i][j-1] + 1
        result = 0
        
        for j in range(len(mat[0])):
            stack = []
            total = 0
            for i in range(len(mat)):
                height = 1
                while len(stack)>0 and stack[-1][0]>row[i][j]:
                    total -= stack[-1][1]*(stack[-1][0] - row[i][j])
                    height += stack[-1][1]
                    stack.pop()
                total += row[i][j]
                result += total
                stack.append([row[i][j],height])
        return result
        
        
        
        
        
        

class Solution:
    def numSubmat(self, mat: List[List[int]]) -> int:
        total_sub_matrix = 0
        for row in range(len(mat)):
            for col in range(len(mat[0])):

                if mat[row][col] == 1:

                    max_col = len(mat[0])
                    for sub_row in range(row, len(mat)):
                        for sub_col in range(col, max_col):
                            if mat[sub_row][sub_col] == 0:
                                max_col = sub_col
                                break
                            
                            total_sub_matrix += 1
        return total_sub_matrix

class Solution:
    def numSubmat(self, mat: List[List[int]]) -> int:
        M = len(mat)
        N = len(mat[0])
        
        res = 0
        
        for i in range(M):
            r = [1] * N
            for j in range(i, M):
                r = [r[k] & mat[j][k] for k in range(N)]
                res += self.countOneRow(r)
        return res
    
    def countOneRow(self, r):
        res = length = 0
        for i, x in enumerate(r):
            length = 0 if x == 0 else length + 1
            res += length
        return res

class Solution:
    def numSubmat(self, mat):
        m, n = len(mat), len(mat[0])
        dp = [[None for i in range(n)] for j in range(m)]
        
        for i in range(m):
            count = 0
            
            for j in range(n-1, -1, -1):
                if mat[i][j]:
                    count += 1
                else:
                    count = 0
                dp[i][j] = count
        
        res = 0
        for i in range(m):
            for j in range(n):
                min_val = float('inf')
                
                for k in range(i, m):
                    min_val = min(min_val, dp[k][j])
                    res += min_val
                    
        return res

class Solution:
    def numSubmat(self, mat: List[List[int]]) -> int:
        n = len(mat); m = len(mat[0])
        arr = mat.copy()
        for i in range(n):
            c = 0
            for j in range(m):
                if mat[i][j]:
                    c += 1
                else:
                    c = 0
                arr[i][j] = c
        
        ans = 0
        for i in range(n):
            for j in range(m):
                x = sys.maxsize
                for k in range(i, n):
                    x = min(x, arr[k][j])
                    ans += x
        
        return ans

class Solution:
    def numSubmat(self, mat: List[List[int]]) -> int:
        
        m,n = len(mat), len(mat[0])

        for i in range(m):
            for j in range(n-2,-1,-1):
                if mat[i][j] == 1:
                    mat[i][j]+= mat[i][j+1]

        c = 0
        for i in range(m):
            for j in range(n):
                min_ = mat[i][j]
                for d in range(i,m):
                    if not mat[i][j]:
                        continue
                    min_ = min(min_, mat[d][j])
                    c = c + min_

        return (c)



from collections import defaultdict

class Solution:
    def numSubmat(self, mat: List[List[int]]) -> int:
        
        
        n,m=len(mat),len(mat[0])
        cnt=0
        def count(arr):
            cnt=[0]*len(arr)
            if arr[0]==1:
                cnt[0]=1
            for i in range(1,len(arr)):
                if arr[i]==arr[i-1]==1:
                    cnt[i]=cnt[i-1]+1
                elif arr[i]==1:
                    cnt[i]=1
                else:
                    cnt[i]=0
            return sum(cnt)
                
        ans=0
        
        for left in range(m):
            c=[1 for i in range(n)]
            for right in range(left,m):                
                for i in range(n):
                    c[i]=c[i] and mat[i][right]
                ans+=count(c)
                  
        return ans
                    
                
                


class Solution:
    def numSubmat(self, mat: List[List[int]]) -> int:
        n, m = len(mat), len(mat[0])
        accs = []
        
        for i in range(n):
            acc = [0]
            
            for j in range(m):
                acc.append(acc[-1]+mat[i][j])
            
            accs.append(acc)
        
        ans = 0
        
        for i in range(m):
            for j in range(i, m):
                cnt = 0
                
                for k in range(n):
                    if accs[k][j+1]-accs[k][i]==j-i+1:
                        cnt += 1
                    else:
                        ans += cnt*(cnt+1)//2
                        cnt = 0
        
                ans += cnt*(cnt+1)//2
        
        return ans

class Solution:
    def numSubmat(self, mat: List[List[int]]) -> int:      
        mat = [[0] + row for row in mat]
        m, n = len(mat), len(mat[0])
        result = 0
        for i, row in enumerate(mat):
            stack = []
            count = [0] * n
            for j in range(n):
                if row[j] and i:
                    row[j] += mat[i - 1][j]
                while stack and row[stack[-1]] > row[j]:
                    stack.pop()
                if j and row[j]:
                    count[j] = count[stack[-1]] + row[j] * (j - stack[-1])
                    result += count[j]
                stack.append(j)
        return result
        
        
        
#         m, n = len(mat), len(mat[0])
#         for i in range(1, m):
#             for j in range(n):
#                 if mat[i][j]:
#                     mat[i][j] += mat[i - 1][j]
#         result = 0
#         for i in range(m):
#             for k in range(i, m):
#                 height = k - i + 1
#                 width = 0
#                 for j in range(n):
#                     if mat[k][j] >= height:
#                         width += 1
#                         result += width
#                     else:
#                         width = 0
#         return result


class Solution:
    def numSubmat(self, mat: List[List[int]]) -> int:
        m, n = len(mat), len(mat[0])
        count = 0
        for left in range(n):
            row_sums = [0 for _ in range(m)]
            for right in range(left, n):
                consec_count = 0
                width = right - left + 1
                for bottom in range(m):
                    row_sums[bottom] += mat[bottom][right]
                    if row_sums[bottom] != width:
                        consec_count = 0
                    else:
                        consec_count += 1
                        count += consec_count
        return count



class Solution:
    def numSubmat(self, mat: List[List[int]]) -> int:
        ans = 0
        N = len(mat)
        M = len(mat[0])
        row = 0 
        col = 0
        for row in range(N):
            for col in range(M):
                if mat[row][col] == 0:
                    continue
                else:
                    i = row
                    j = col
                    n = N 
                    while j < M:
                        if mat[i][j] == 0 or i == n:
                            n = i
                            i = row
                            j += 1
                        elif i+1 == N:
                            i = row
                            j += 1
                            ans += 1
                        else:
                            ans += 1
                            i += 1
        return ans


class Solution:
    def numSubmat(self, mat: List[List[int]]) -> int:
        n = len(mat)
        m = len(mat[0])
        cumones = [[0]*m for x in range(n)]
        for i in range(n):
            for j in range(m-1, -1, -1):
                if mat[i][j] == 1:
                    cumones[i][j] = 1+(cumones[i][j+1] if j < m-1 else 0)
        ct = 0
        for i in range(n):
            for j in range(m):
                minw = sys.maxsize
                for k in range(i,n):
                    if mat[i][j] == 1:
                        minw = min(minw, cumones[k][j])
                        ct += minw
        return ct

class Solution:
    def numSubmat(self, mat: List[List[int]]) -> int:
        # O(m ^ 2 * n); Space: O(mn)
        if not mat:
            return 0
        
        m, n = len(mat), len(mat[0])
        
        dp = [[0] * (n + 1) for _ in range(m + 1)]
        
        res = 0
        for i in range(1, m + 1):
            for j in range(1, n + 1):
                if mat[i - 1][j - 1]:
                    dp[i][j] = dp[i][j - 1] + 1 # walk left
                    res += dp[i][j]
                    # walk above
                    min_ones = dp[i][j]
                    for k in range(i - 1, -1, -1):
                        min_ones = min(min_ones, dp[k][j])
                        res += min_ones
        return res

class Solution:
    def numSubmat(self, mat: List[List[int]]) -> int:
        M, N = len(mat), len(mat[0])
        res = 0
        for up in range(M):
            h = [1 for i in range(N)]
            for down in range(up, M):
                for col in range(N):
                    h[col] &= mat[down][col]
                res += self.oneArray(h)
        return res
                
    
    def oneArray(self, arr):
        res = length = 0
        for a in arr:
            length = 0 if a == 0 else length + 1
            res += length
        return res

class Solution:
    def numSubmat(self, mat: List[List[int]]) -> int:
        m = len(mat)
        n = len(mat[0])
        pre = [[0]*(n+1) for _ in range(m)]
        
        for row in range(m):
            for col in range(1, n+1):
                pre[row][col] = mat[row][col-1] + pre[row][col-1]
        
        ans = 0
        for col1 in range(n):
            for col2 in range(col1+1, n+1):
                local_ans = 0
                curr_stack = 0
                for row in range(m):
                    if pre[row][col2] - pre[row][col1] == col2-col1:
                        curr_stack += 1
                        local_ans += curr_stack
                    else:
                        curr_stack = 0
                ans += local_ans
        return ans

class Solution:
    def numSubmat(self, A: List[List[int]]) -> int:
        m, n = len(A), len(A[0])
        
        res = 0
        
        for i in range(m):
            r = [1] * n
            for j in range(i, m):
                for k in range(n):
                    r[k] &= A[j][k]
                    
                res += self.count(r)
                
        return res
    
    def count(self, r):
        res = head = 0
        for n in r:
            head = head + 1 if n else 0
            res += head
        return res

class Solution:
    def numSubmat(self, mat: List[List[int]]) -> int:
        ans = 0
        for i in range(len(mat)):
            for j in range(len(mat[0])):
                row,col = 0,0
                if mat[i][j] == 1:
                    while row<len(mat)-i and mat[i+row][j] == 1:
                        row += 1
                    while col<len(mat[0])-j and mat[i][j+col] == 1:
                        col += 1
                    cnt,col_min = 0, col
                    for ii in range(row):
                        for jj in range(min(col_min,col)):
                            if mat[i+ii][j+jj]==1:
                                cnt += 1
                            else:
                                col_min = jj
                                break
                    print((i,j,cnt))
                    ans += cnt
        return ans


class Solution:
    def numSubmat(self, mat: List[List[int]]) -> int:
        ans = 0
        N, M = len(mat), len(mat[0])
        for i in range(N):
            mask  = mat[i]
            for j in range(i, N):
                if j > i:
                    mask = [int(i&j) for i, j in zip(mask, mat[j])]
                cnt = 0
                for k in mask:
                    if k == 1:
                        cnt += 1
                    else:
                        ans += cnt * (cnt+1) // 2
                        cnt = 0
                ans += cnt * (cnt+1) // 2
        return ans

class Solution:
    def numSubmat(self, mat: List[List[int]]) -> int:
        ans = 0
        N, M = len(mat), len(mat[0])
        for i in range(N):
            mask  = mat[i]
            for j in range(i, N):
                if j > i:
                    mask = [int(i&j) for i, j in zip(mask, mat[j])]
                cnt = 0
                for k in mask:
                    if k == 1:
                        cnt += 1
                    else:
                        ans += cnt * (cnt+1) // 2
                        cnt = 0
                ans += cnt * (cnt+1) // 2
        return ans




class Solution:
    def numSubmat(self, mat):
        if not mat:
            return 0
        row, col = len(mat), len(mat[0])
        for r in range(row):
            for c in range(col):
                if mat[r][c] >= 1 and r:
                    mat[r][c] += mat[r-1][c] 
        answer = 0
        for row in mat:
            stack = [-1]
            num_submatrices = 0 
            for i, num in enumerate(row):
                while stack[-1] != -1 and num <= row[stack[-1]]:
                    larger_num_idx = stack.pop()
                    num_submatrices -= row[larger_num_idx] * (larger_num_idx-stack[-1])
                num_submatrices += num * (i-stack[-1])
                answer += num_submatrices
                stack.append(i)
        return answer 


class Solution:
    # This idea is to conver the problem from the 2d version to 1d version
    def numSubmat(self, mat: List[List[int]]) -> int:
        res = 0
        m, n = len(mat), len(mat[0])
        
        def v1d(h):
            ans = 0
            length = 0
            for v in h:
                length = length + 1 if v else 0
                ans += length
            return ans

        for i in range(m):
            h = [1]*n
            for idown in range(i, m):
                for j in range(n):
                    h[j] &= mat[idown][j]
                res += v1d(h)
        return res
            
        
        
        
        
    # this method start with 1x1, and then try to extend a small matrix
    # to bigger matrix by extending row and collum by 1.
    # The problem is that, it will check a lot of duplicates
    # TEL
    def numSubmat_dp_style(self, mat: List[List[int]]) -> int:
        allones = set()
        m, n = len(mat), len(mat[0])
        q = collections.deque()
        for i, j in itertools.product(range(m), range(n)):
            if mat[i][j]:
                q.append((i, j, 1, 1))
                allones.add((i, j, 1, 1))
        
        while q:
            i, j, r, c = q.popleft()
            # check r+1, c+1
            if i+r < m and (i+r, j, 1, c) in allones:
                q.append((i, j, r+1, c))
                allones.add((i, j, r+1, c))
            
            if j + c < n and (i, j+c, r, 1) in allones:
                q.append((i, j, r, c+1))
                allones.add((i, j, r, c+1))
        return len(allones)

class Solution:
    def numSubmat(self, mat: List[List[int]]) -> int:
        
        m = len(mat)
        if not m: return 0
        n = len(mat[0])
        
        dp = [[0] * n for _ in range(m)]
        
        for i in range(m):
            for j in range(n):
                if mat[i][j] == 1:
                    if j == 0:
                        dp[i][j] = 1
                    else:
                        dp[i][j] = dp[i][j-1] + 1
        res = 0    
        for i in range(m):
            for j in range(n):
                if mat[i][j] == 0:
                    continue
                row = i
                minWidth =math.inf
                while row >= 0 and mat[i][j]:
                    minWidth = min(minWidth, dp[row][j])
                    res += minWidth
                    row -= 1
        return res


class Solution:
    def numSubmat(self, mat: List[List[int]]) -> int:
        n = len(mat)
        m = len(mat[0])
        ar = [[0 for j in range(m)]for i in range(n)]
        c = 0
        for i in range(n):
            c = 0 
            for j in range(m-1,-1,-1):
                if mat[i][j] == 1:
                    c += 1
                else:
                    c = 0
                ar[i][j] = c
        
        ans = 0
        for i in range(n):
            for j in range(m):
                x = float('inf')
                for k in range(i,n):
                    x = min(x,ar[k][j])
                    ans += x
        
        return ans

class Solution:
    def numSubmat(self, mat: List[List[int]]) -> int:
        M, N = len(mat), len(mat[0])
        res = 0
        for top in range(M):
            h = [1 for _ in range(N)]
            for bottom in range(top, M):
                for j in range(N):
                    h[j] &= mat[bottom][j]
                res += self.count1D(h)
        return res
    
    def count1D(self, array):
        res, length = 0, 0
        for i in range(len(array)):
            if array[i] == 0:
                length = 0
            else:
                length += 1
            res += length
        return res

class Solution:
    def numSubmat(self, mat: List[List[int]]) -> int:
        r, c = len(mat), len(mat[0])
        res = 0
        dp = [[0] * (c + 1) for _ in range(r + 1)]
        for i in range(1, r + 1):
            for j in range(1, c + 1):
                if mat[i - 1][j - 1]:
                    dp[i][j] = dp[i][j - 1] + 1
                    res += dp[i][j]
                    min_ones = dp[i][j]
                    for k in range(i - 1, -1, -1):
                        min_ones = min(min_ones, dp[k][j])
                        res += min_ones
        return res


#https://www.youtube.com/watch?v=8HYXkNB39KA
#https://www.youtube.com/watch?v=hrd-MEcZkOI&feature=youtu.be
class Solution:
    def numSubmat(self, mat: List[List[int]]) -> int:
        rows=len(mat)
        cols=len(mat[0])
        for r in range(rows):
            for c in range(cols):
                if mat[r][c]:
                    if c>0:
                        mat[r][c]=mat[r][c-1]+1
        
        submatrices=0
        for r in range(rows):
            for c in range(cols):
                if mat[r][c]:
                    row=r
                    min_value=mat[r][c]
                    while row<rows and mat[r][c]:
                        min_value=min(min_value,mat[row][c])
                        submatrices+=min_value
                        row+=1
        return submatrices              
                        
        
            
             
                    

        
                     
        


class Solution:
    def helper(self, mat, a, b):
        N = len(mat)
        M = len(mat[0])
        
        bound = M
        count = 0
        
        for r in range(a, N):
            for c in range(b, bound):                
                if mat[r][c] == 1: 
                    if (a,b) == (0,0):
                        print(\"!! rc\", r,c)
                    count += 1
                else:
                    bound = c
                    break
        return count
                
        
        
    def numSubmat(self, mat: List[List[int]]) -> int:
        N = len(mat)
        if N == 0: return 0
        M = len(mat[0])
        count = 0 
        
        for r in range(N):
            for c in range(M):
                out = self.helper(mat, r, c)
                print(\"!\", r, c, out)
                count += out
        
        return count

class Solution:
    def numSubmat(self, A: List[List[int]]) -> int:
        r = len(A)
        c = len(A[0])
        dp = [[0]*(c+1) for _ in range(r+1)]
        for i in range(r):
            dp[i][0] = 0
            for j in range(c):
                dp[i][j+1] = dp[i][j] + A[i][j]
        ans = 0
        for lhs in range(c):
            for rhs in range(lhs, c):
                amt = 0
                for i in range(r):
                    if dp[i][rhs+1] - dp[i][lhs] == rhs-lhs+1:
                        amt += 1 
                    else:
                        amt = 0
                    ans += amt
        return ans
        
        
        
\"\"\"
For each row i, create an array nums where:

mat[i][j] == 0 then nums[j] = 0 else nums[j] = nums[j-1] + 1

In row i, the number of rectangles between column j and k(inclusive) and ends in row i
is equal to sum(min(nums[j,...,idx])) where idx go from j to k


in row i the number of rectangles between column j and k that ends in row i is equal to
sum ( min ( row[j:idx+1])) for idx in range(j, k)

expected solution is O(n*3)
\"\"\"

class Solution:
    def numSubmat(self, mat: List[List[int]]) -> int:
        row = len(mat)
        col = len(mat[0])
        
        dp = [[None]*col for _ in range(row)]
        
        for i in range(row):
            count = 0
            for j in range(col):
                if mat[i][j] == 1:
                    count += 1
                else:
                    count = 0
                dp[i][j] = count
        
        res = 0
        for i in range(row):
            for j in range(col):
                mn = float('inf')
                for k in range(i, row):
                    mn = min(mn, dp[k][j])
                    res += mn
        return res


class Solution:
    def numSubmat(self, A: List[List[int]]) -> int:
        m, n = len(A), len(A[0])
        h = [0] * n
        res = 0
        
        for i in range(m):
            
            stk = []
            psum = [0] * n

            for j in range(n):
                h[j] = h[j] + 1 if A[i][j] else 0
                
                while stk and h[stk[-1]] >= h[j]: stk.pop()
                    
                k = stk[-1] if stk else -1
                ksum = psum[k] if stk else 0
                
                psum[j] = ksum + h[j] * (j - k)
                
                stk.append(j)
                
            res += sum(psum)
                
        return res

class Solution:
    def numSubmat(self, mat: List[List[int]]) -> int:
        r = len(mat)
        c = len(mat[0])

        for i in range(r): 
            for j in range(c-2,-1,-1):
                if mat[i][j] == 1:
                    if j < (c-1):
                        mat[i][j] += mat[i][j+1]
        
        res = 0
        print(mat)
        
        for i in range(r):
            for j in range(c):
                m = float('inf')
                for k in range(i,r):
                    m = min(m, mat[k][j])
                    res += m
        
        return res

class Solution:
    def numSubmat(self, mat: List[List[int]]) -> int:
        m = len(mat)
        n = len(mat[0])
        
        ans = 0
        for i1 in range(m):
            dp = [0] * n
            for i2 in range(i1, m):
                for j in range(n):
                    dp[j] += mat[i2][j]
                
                l = 0
                j = 0
                while j < n:
                    if dp[j] == i2 - i1 + 1:
                        l += 1
                    else:
                        ans += l * (l + 1) // 2
                        l = 0
                    
                    j += 1
                
                if l > 0:
                    ans += l * (l + 1) // 2
        
        return ans

class Solution:
    def numSubmat(self, mat: List[List[int]]) -> int:
        m = len(mat)
        n = len(mat[0])
        
        
        def count_submatrices(r, c):
            count = 0
            bound = n
            for i in range(r, m):
                for j in range(c, bound):
                    if j >= bound:
                        continue
                    elif mat[i][j] == 1:
                        count += 1
                    else:
                        bound = j
            return count
            
        # return count_submatrices(0, 0)
        total_count  = 0
        for r, row in enumerate(mat):
            for c, cell in enumerate(row):
                total_count += count_submatrices(r, c)

        return total_count

class Solution:
    def numSubmat(self, mat: List[List[int]]) -> int:
        def counts(nums):
            endhere = [0]*len(nums)
            st = []
            for i, num in enumerate(nums):
                while st and nums[st[-1]] >= num:
                    st.pop()
                if not st:
                    endhere[i] = num * (i + 1)
                else:
                    prev_idx = st[-1]
                    endhere[i] = endhere[prev_idx]
                    endhere[i] += num*(i - prev_idx)
                st.append(i)
            return sum(endhere)
        rows = mat[0][:]
        ans = counts(rows[:])
        # print(ans)
        for i in range(1, len(mat)):
            for j in range(len(mat[0])):
                if mat[i][j] == 1:
                    rows[j] += 1
                else:
                    rows[j] = 0
            # print(rows)
            ans += counts(rows[:])
            # print(ans)
        return ans
                    


class Solution:
    def numSubmat(self, mat: List[List[int]]) -> int:
        m, n = len(mat), len(mat[0])
        
        #precipitate mat to histogram 
        for i in range(m):
            for j in range(n):
                if mat[i][j] and i > 0: 
                    mat[i][j] += mat[i-1][j] #histogram 
        
        ans = 0
        for i in range(m):
            stack = [] #mono-stack of indices of non-decreasing height
            cnt = 0
            for j in range(n):
                while stack and mat[i][stack[-1]] > mat[i][j]: 
                    jj = stack.pop()                          #start
                    kk = stack[-1] if stack else -1           #end
                    cnt -= (mat[i][jj] - mat[i][j])*(jj - kk) #adjust to reflect lower height

                cnt += mat[i][j] #count submatrices bottom-right at (i, j)
                ans += cnt
                stack.append(j)

        return ans

class Solution:
    def numSubmat(self, mat: List[List[int]]) -> int:
        m = len(mat)
        n = len(mat[0])
        tot = 0
        for i in range(m):
            prev = []
            for j in range(n):
                if not mat[i][j]:
                    prev = []
                    continue
                if i > 0:
                    mat[i][j] += mat[i - 1][j]
                h = mat[i][j]
                tot += h
                for p in range(len(prev) - 1, -1, -1):
                    if prev[p] > h:
                        prev[p] = h
                    tot += prev[p]
                prev.append(h)
        return tot


class Solution:
    def helper(self, heights, n):
        stack = []
        res = [0] * n
        for i in range(n):
            while stack and heights[stack[-1]] >= heights[i]:
                stack.pop()
            if stack:
                prev = stack[-1]
                res[i] = res[prev] + heights[i] * (i - prev)
            else:
                res[i] = heights[i] * (i + 1)
            stack.append(i)
        return sum(res)
    def numSubmat(self, mat: List[List[int]]) -> int:
        m, n = len(mat), len(mat[0])
        heights = [[0] * n for _ in range(m)]
        res = 0
        for j in range(n):
            if mat[0][j] == 1:
                heights[0][j] = 1
        for i in range(1, m):
            for j in range(n):
                if mat[i][j] == 1:
                    heights[i][j] = heights[i-1][j] + 1
        for i in range(m):
            res += self.helper(heights[i], n)
        return res

class Solution:
  #  def helper(self, l):
  #      num = 0
  #      ct = 0
  #      for j in range(len(l)):
  #          if l[j] == 1:
  #              ct += 1
  #          else:
  #              ct = 0
  #          num += ct
  #      
  #      return num
  #  
  #
  #  def numSubmat(self, mat: List[List[int]]) -> int:
  #      m = len(mat)
  #      n = len(mat[0])
  #      tot_sum = 0
  #      for i1 in range(m):
  #          l = [1]*n
  #          for i2 in range(i1, m):
  #              for j in range(n):
  #                  l[j] &= mat[i2][j]
  #              tot_sum += self.helper(l)
  #              
  #      return tot_sum
  #  
    
    def helper(self, arr):
        tracker = [0] * len(arr)
        stack = []
        
        for i in range(len(arr)):
            while stack and arr[stack[-1]] >= arr[i]:
                stack.pop()
            if stack:
                tracker[i] = tracker[stack[-1]]
                tracker[i] += arr[i] * (i - stack[-1])
            else:
                tracker[i] = arr[i] * (i + 1)
            stack.append(i)
        
        return sum(tracker)
    
    def numSubmat(self, mat: List[List[int]]) -> int:
        m = len(mat)
        n = len(mat[0])
        column_track = [0] * n
        res = 0
        
        for i in range(m):
            for j in range(n):
                column_track[j] = 0 if mat[i][j] == 0 else column_track[j] + 1
            res += self.helper(column_track)
        
        return res
            
    
        
            


class Solution:
    def numSubmat(self, mat: List[List[int]]) -> int:
        m,n,res = len(mat), len(mat[0]),0
        histogram = [0] * (n+1)
        for i in range(m):
            stack,dp = [-1], [0]*(n+1)
            for j in range(n):
                if mat[i][j] == 0:
                    histogram[j] = 0
                else:
                    histogram[j] += 1
            
                while histogram[j] < histogram[stack[-1]]:
                    #print(stack)
                    stack.pop()
                    #print(stack)

                #print(stack)
                dp[j] = dp[stack[-1]] + histogram[j] * (j-stack[-1])
                stack.append(j)
                
            res += sum(dp)
            
        return res

class Solution:
    def numSubmat(self, mat: List[List[int]]) -> int:
        def pom(tab):
            stack = []
            sums = [0] * len(tab)
            for i in range(len(tab)):
                while len(stack) > 0 and tab[stack[-1]] > tab[i]:
                    stack.pop()
                if len(stack) == 0:
                    sums[i] = (i + 1) * tab[i]
                else:
                    sums[i] = sums[stack[-1]] + tab[i] * (i - stack[-1])
                stack.append(i)

            return sum(sums)
        
        n_rows = len(mat)
        n_cols = len(mat[0])
        h = [0] * n_cols
        res = 0
        for row in mat:
            for i in range(len(row)):
                if row[i] == 1:
                    h[i] += 1
                else:
                    h[i] = 0
            res += pom(h)
        
        return res

class Solution:
    def numSubmat(self, mat: List[List[int]]) -> int:
        m, n = len(mat), len(mat[0])
        
        #precipitate mat to histogram 
        for i in range(m):
            for j in range(n):
                if mat[i][j] and i > 0: 
                    mat[i][j] += mat[i-1][j] #histogram 
        
        ans = 0
        for i in range(m):
            stack = [] #mono-stack of indices of non-decreasing height
            cnt = 0
            for j in range(n):
                while stack and mat[i][stack[-1]] > mat[i][j]: 
                    jj = stack.pop()                          #start
                    kk = stack[-1] if stack else -1           #end
                    cnt -= (mat[i][jj] - mat[i][j])*(jj - kk) #adjust to reflect lower height

                cnt += mat[i][j] #count submatrices bottom-right at (i, j)
                ans += cnt
                stack.append(j)

        return ans


class Solution:
    def numSubmat(self, mat: List[List[int]]) -> int:
        M, N = len(mat), len(mat[0])
        for i in range(1, M):
            for j in range(N):
                if mat[i][j]:
                    mat[i][j] += mat[i-1][j]
        
        # 3, 5, 2, 1, 0, 4
        # count[0] = 3 * (0 + 1)
        # count[1] = 5 * (1 - 0) + count[0]
        # count[2] = 2 * (2 + 1)
        # count[3] = 1 * (3 + 1)
        
        result = 0
        for row in mat:
            count = [0] * N
            stk = []
            for i, e in enumerate(row):
                while stk and row[stk[-1]] >= e:
                    stk.pop()
                
                if stk:
                    count[i] = count[stk[-1]] + e * (i - stk[-1])
                else:
                    count[i] = e * (i + 1)
                
                stk.append(i)
            result += sum(count)
        return result

class Solution:
    def numSubmat(self, mat: List[List[int]]) -> int:
        if not mat:
            return 0
        m = len(mat)
        n = len(mat[0])
        
        for y in range(m):
            for x in range(n):
                if mat[y][x] and y > 0:
                    mat[y][x]  += mat[y-1][x]
                    
        ans = 0
        for y in range(m):
            stack = []
            cnt = 0
            for x in range(n):
                # stack is the last element 
                while stack and mat[y][stack[-1]] > mat[y][x]:
                    #########  remove the top row from the next calculation of adding cnt 
                    # * * * 
                    #
                    # * * * *
                    # * * * *
                    
                    prev_hist_end = stack.pop()
                    prev_hist_start = stack[-1] if stack else -1
                    # difference in historgram height * width
                    cnt -= (prev_hist_end - prev_hist_start)*(mat[y][prev_hist_end] - mat[y][x])
                cnt += mat[y][x]
                ans += cnt
                stack.append(x)
                
        return ans

class Solution:
    def numSubmat(self, mat: List[List[int]]) -> int:
        if not mat: return 0
        m, n = len(mat), len(mat[0])
        ans = 0
        colCount = [0] * n
        for i in range(m):
            rowCount = 0
            colCount1 = [0] * n
            for j in range(n):
                if mat[i][j]:
                    rowCount += 1
                    colCount1[j] = colCount[j] + 1
                    minColCount = math.inf
                    for k in range(j, j - rowCount, -1):
                        minColCount = min(minColCount, colCount1[k])
                        ans += minColCount
                else:
                    colCount1[j] = 0
                    rowCount = 0
            colCount = colCount1
        return ans


class Solution:
#     https://leetcode.com/problems/count-submatrices-with-all-ones/discuss/721999/Python3-O(MN)-histogram-model
    # Should pay more attention to this one
    # Histogram model. First, stack all the rows, (prefix sum vertically)
    # And then use a non-decreasing stack for each row
    # Cumulate count to res, unless lower height appears, adjust the height
    # Using non-decreasing stack and cumulative, each time, you can add current height to each of the previous same row possibility 
    # We rule out the non-continuous
    def numSubmat(self, mat: List[List[int]]) -> int:
        m,n = len(mat),len(mat[0])
        for r in range(m):
            for c in range(n):
                if mat[r][c] and r > 0:
                    mat[r][c] += mat[r-1][c]
        res = 0
        for r in range(m):
            count = 0
            stack = []
            for c in range(n):
                while stack and mat[r][stack[-1]] > mat[r][c]:
                    j = stack.pop()
                    w = stack[-1] if stack else -1
                    count -= (mat[r][j]-mat[r][c])*(j-w)
                    
                count += mat[r][c]
                res += count
                stack.append(c)
        return res
                

            


class Solution:
    def numSubmat(self, mat: List[List[int]]) -> int:
        
        ans = 0
        M = len(mat)
        if M==0:
            return 0
        N = len(mat[0])
        
        count = [0 for _ in range(N)]
        ans = 0
        for i in range(M):
            rowcount = 0
            for j in range(N):
                if mat[i][j]==1:
                    count[j] += 1
                    rowcount += 1
                    
                    minV = 1<<30
                    for k in range(j, j-rowcount, -1):
                        minV=min(minV, count[k])
                        ans += minV
                    
                else:
                    rowcount = 0
                    count[j] = 0
                    
        return ans
                    

                


class Solution:
    def numSubmat1(self, mat: List[List[int]]) -> int:
        m,n,res=len(mat),len(mat[0]),0
        histogram=[0]*(n)
        for i in range(m):
            stack,dp=[],[0]*(n)
            for j in range(n):
                histogram[j]=0 if mat[i][j]==0 else histogram[j]+1
                while stack and histogram[j]<histogram[stack[-1]]: #increasing stack
                    stack.pop()
                if stack:
                    dp[j]=dp[stack[-1]]+histogram[j]*(j-stack[-1]) # Important!!
                else:
                    dp[j] = histogram[j]*(j+1)
                stack.append(j)
            res+=sum(dp)
            print (res)
        return res
    def numSubmat(self, mat: List[List[int]]) -> int:
        m,n = len(mat),len(mat[0])
        
        count = 0 
        hist = [0]*(n)
        for i in range(m):
            
            dp  = [0]*n
            for j in range(n):
                if mat[i][j] == 1:
                    hist[j] +=1
                else:
                    hist[j] = 0
            stack = []
            for j,h in enumerate(hist):
                while stack and hist[stack[-1]]  >= h:
                    stack.pop()
                if stack:
                    dp[j]=dp[stack[-1]]+hist[j]*(j-stack[-1]) 
                else:
                    dp[j] = hist[j]*(j+1)
                stack.append(j)
            count += sum(dp)
            print (count)
        return count 

class Solution:
    def numSubmat(self, mat: List[List[int]]) -> int:
        
        lim1 = len(mat)
        lim2 = len(mat[0])
        
        hz = [[0 for j in range(0,lim2)] for i in range(0,lim1)]
        
        t = 0
        for i in range(lim1-1,-1,-1):
            for j in range(lim2-1,-1,-1):
                if mat[i][j]!=0:
                    if j<lim2-1:
                        hz[i][j]+=hz[i][j+1]+1
                    else:
                        hz[i][j]=1
        
        vt = [[0 for j in range(0,lim2)] for i in range(0,lim1)]
        
        for i in range(0,lim1):
            for j in range(0,lim2):
                if hz[i][j]!=0:
                    mn = 99999999999
                    for k in range(i,lim1):
                        if hz[k][j]==0:
                            break
                        else:
                            if hz[k][j]<mn:mn = hz[k][j]
                    
                        t+=mn
        
        return t
        


class Solution:
    def numSubmat(self, mat: List[List[int]]) -> int:
        m, n = len(mat), len(mat[0])
        
        #precipitate mat to histogram 
        for r in range(m):
            for c in range(n):
                if mat[r][c] and r > 0: 
                    mat[r][c] += mat[r-1][c] #histogram 
        
        res = 0
        for r in range(m):
            stack = [] # mono-stack of indices of non-decreasing height for current row
            dp = 0 # number of submatrices with all 1's ending at (r,c-1) so far
            for c in range(n):
                while stack and mat[r][stack[-1]] > mat[r][c]: 
                    start = stack.pop()                        #start
                    end = stack[-1] if stack else -1           #end
                    # difference in height between the taller bar and the current bar * width to bar before taller bar
                    dp -= (mat[r][start] - mat[r][c])*(start - end) #adjust to reflect lower height

                dp += mat[r][c] #count submatrices bottom-right at (i, j)
                res += dp
                stack.append(c)

        return res

class Solution:
    def numSubmat(self, mat: List[List[int]]) -> int:
        m, n = len(mat), len(mat[0])
        dp = [[0] * n for _ in range(m)]
        res = 0
        for i in range(m):
            dp[i][0] = 1 if mat[i][0] == 1 else 0
            res += dp[i][0]
            mini = dp[i][0]
            for k in range(i-1, -1, -1):
                mini = min(mini, dp[k][0])
                res += mini
                if mini == 0:
                    break
            
            for j in range(1, n):
                if mat[i][j] == 1:
                    dp[i][j] = dp[i][j-1] + 1
                    res += dp[i][j]
                    
                    mini = dp[i][j]
                    for k in range(i-1, -1, -1):
                        mini = min(mini, dp[k][j])
                        res += mini
                        if mini == 0:
                            break
        return res

class Solution:
    def numSubmat(self, mat: List[List[int]]) -> int:
        if not mat: return 0
        
        rows, cols = len(mat), len(mat[0])
        height = [0] * cols
        output = 0
        for r in range(rows):
            for c in range(cols):
                if mat[r][c] == 0:
                    height[c] = 0
                else:
                    height[c] += 1
                    v = height[c]
                    for i in range(c, -1, -1):
                        if height[i] == 0: break
                        v = min(v, height[i])
                        output += v
        return output
    
    
#     public int numSubmat(int[][] mat) {
#         int m = mat.length, n = mat[0].length, height[] = new int[n], res = 0; 
#         for (int i = 0; i < m; i++) {
#             for (int j = 0; j < n; j++) {
#                 height[j] = mat[i][j] == 0 ? 0 : height[j] + 1;   //  height of histogram;
#                 for (int k = j, min = height[j]; k >= 0 && min > 0; k--) {
#                     min = Math.min(min, height[k]);
#                     res += min;
#                 }
#             }
#         }
#         return res;
#     }


        
        
        1 + 1 + 2 + 1 + 1 + 3 + 2+ 2
        
        


class Solution:
    def numSubmat(self, mat: List[List[int]]) -> int:
          
        h, w = len(mat), len(mat[0])
        
        # dp table:
        # record the maximum length of continuous 1 from left-most column to specified column
        dp_acc_of_1 = [ [ 0 for _ in range(w)] for _ in range(h) ]
        
        for y in range(h):
            for x in range(w):
                
                if x == 0:
                    # left-most column
                    dp_acc_of_1[y][x] = mat[y][x]
                    
                else:
                    # not left-most column
                    if mat[y][x] == 1:
                        dp_acc_of_1[y][x] = dp_acc_of_1[y][x-1] + 1
                        
        
        counter_of_rectangle = 0
        
        for y in range(h):
            for x in range(w):
                
                # update the total number of rectangle, whose bottom right anchor point is [y][x]
                
                minimum_width = dp_acc_of_1[y][x]
                
                for h_idx in range(y, -1, -1):
                    
                    minimum_width = min(minimum_width, dp_acc_of_1[h_idx][x])
                    counter_of_rectangle += minimum_width
                    
                    if minimum_width == 0:
                        # no chance to make rectangle
                        break
                        
        return counter_of_rectangle

class Solution:
    def numSubmat(self, mat: List[List[int]]) -> int:
        acc, his = 0, [0] * len(mat[0])
        for i, row in enumerate(mat):
            for j, v in enumerate(row):
                his[j] = his[j] + 1 if v else 0
                cap = float('inf')
                for height in his[:j + 1][::-1]:
                    cap = min(cap, height)
                    if not cap:
                        break
                    acc += cap
                # print(i, j, acc)
        return acc

class Solution:
    def numSubmat(self, mat: List[List[int]]) -> int:
        h, w = len(mat), len(mat[0])
        
        # dp table:
        # record the maximum length of continuous 1 from left-most column to specified column
        dp_acc_of_1 = [ [ 0 for _ in range(w)] for _ in range(h) ]
        
        for y in range(h):
            for x in range(w):
                
                if x == 0:
                    # left-most column
                    dp_acc_of_1[y][x] = mat[y][x]
                    
                else:
                    # not left-most column
                    if mat[y][x] == 1:
                        dp_acc_of_1[y][x] = dp_acc_of_1[y][x-1] + 1
                        
        
        counter_of_rectangle = 0
        
        for y in range(h):
            for x in range(w):
                
                # update the total number of rectangle, whose bottom right anchor point is [y][x]
                
                minimum_width = dp_acc_of_1[y][x]
                
                for h_idx in range(y, -1, -1):
                    
                    minimum_width = min(minimum_width, dp_acc_of_1[h_idx][x])
                    counter_of_rectangle += minimum_width
                    
                    if minimum_width == 0:
                        # no chance to make rectangle
                        break
                        
        return counter_of_rectangle

class Solution:
    def numSubmat(self, mat: List[List[int]]) -> int:
        h, w = len(mat), len(mat[0])
        dp_acc_of_1 = [ [ 0 for _ in range(w)] for _ in range(h) ]
        for y in range(h):
            for x in range(w):
                if x == 0:
                    dp_acc_of_1[y][x] = mat[y][x]
                else:
                    if mat[y][x] == 1:
                        dp_acc_of_1[y][x] = dp_acc_of_1[y][x-1] + 1
        counter_of_rectangle = 0
        for y in range(h):
            for x in range(w):               
                minimum_width = dp_acc_of_1[y][x]
                for h_idx in range(y, -1, -1):
                    minimum_width = min(minimum_width, dp_acc_of_1[h_idx][x])
                    counter_of_rectangle += minimum_width
                    
                    if minimum_width == 0:
                        break
        return counter_of_rectangle

class Solution:
    def numSubmat(self, mat: List[List[int]]) -> int:
        row = len(mat)
        col = len(mat[0])
        
        dp = [[0 for _ in range(col)] for _ in range(row)]
        
        # find the length of the left rec at point(i, j)
        for i in range(row):
            for j in range(col):
                if mat[i][j]:
                    dp[i][j] = dp[i][j-1] + 1 if j >= 1 else 1
        
        # from the right end (i,j) = (row_end, col_end) to find height = 1,2...
        res = 0
        for i in range(row):
            for j in range(col):
                leftnum = float(\"inf\")
                for k in range(i, -1, -1):
                    leftnum = min(leftnum, dp[k][j])
                    
                    if leftnum == 0:
                        break
                    res += leftnum
                    
        return res

class Solution:
    def numSubmat(self, mat: List[List[int]]) -> int:
        if not mat:
            return 0
        m, n = len(mat), len(mat[0])
        ret = 0
        height = [0] * n
        for i in range(m):
            for j in range(n):
                height[j] = 0 if not mat[i][j] else height[j] + 1
                if mat[i][j]:
                    h = height[j]
                    for k in range(j, -1, -1):
                        if mat[i][k]:
                            h = min(h, height[k])
                            ret += h
                        else:
                            break
            # print(height)
            # print(ret)
        return ret


class Solution:
    def numSubmat(self, mat: List[List[int]]) -> int:
        
        h, w = len(mat), len(mat[0])
        
        # dp table:
        # record the maximum length of continuous 1 from left-most column to specified column
        dp_acc_of_1 = [ [ 0 for _ in range(w)] for _ in range(h) ]
        
        for y in range(h):
            for x in range(w):
                
                if x == 0:
                    # left-most column
                    dp_acc_of_1[y][x] = mat[y][x]
                    
                else:
                    # not left-most column
                    if mat[y][x] == 1:
                        dp_acc_of_1[y][x] = dp_acc_of_1[y][x-1] + 1
                        
        
        counter_of_rectangle = 0
        
        for y in range(h):
            for x in range(w):
                
                # update the total number of rectangle, whose bottom right anchor point is [y][x]
                
                minimum_width = dp_acc_of_1[y][x]
                
                for h_idx in range(y, -1, -1):
                    
                    minimum_width = min(minimum_width, dp_acc_of_1[h_idx][x])
                    counter_of_rectangle += minimum_width
                    
                    if minimum_width == 0:
                        # no chance to make rectangle
                        break
                        
        return counter_of_rectangle


# create integral sum with each row, reset at 0
# In the row i, number of rectangles between column j and k(inclusive) and ends in row i, is equal to SUM(min(nums[j, .. idx])) where idx go from j to k.

class Solution:
    def numSubmat(self, mat: List[List[int]]) -> int:
        res = 0
        m = mat
        
        for i in range(len(mat)):
            for j in range(len(mat[0])):
                if j > 0 and mat[i][j] == 1: #!j>0
                    m[i][j] = m[i][j - 1] + 1
        
        for j in range(len(mat[0])):
            for i in range(len(mat)):
                mn = m[i][j]

                for k in range(i, -1, -1): # from i to top  
                    mn = min(mn, m[k][j])
                    if mn == 0:
                        break
                    res += mn  #!每看到一个非零，都要加
        return res
                    
        
                


class Solution:
    def numSubmat(self, mat: List[List[int]]) -> int:
        for i in range(1, len(mat)):
            for j in range(len(mat[0])):
                if mat[i][j]:
                    mat[i][j] += mat[i-1][j]
                
        ans = 0
        for i in range(len(mat)):
            stack = []
            cnt = 0
            for j in range(len(mat[0])):
                while stack and mat[i][stack[-1]]>mat[i][j]:
                    last = stack.pop()
                    prev = stack[-1] if stack else -1
                    cnt -= (mat[i][last] - mat[i][j]) * (last - prev)
                cnt += mat[i][j]
                ans += cnt
                stack.append(j)
                
            
        return ans

class Solution:
    def numSubmat(self, mat: List[List[int]]) -> int:
        m, n = len(mat), len(mat[0])
        up = [[0]*n for _ in range(m)]
        count = 0
        for i in range(m):
            for j in range(n):
                if not mat[i][j]:
                    continue
                   
                if i == 0:
                    up[i][j] =  1
                else:
                    up[i][j] = up[i-1][j] + 1 
                    
                k = j 
                min_height = up[i][j]
                while k >= 0 and mat[i][k]:
                    min_height = min(min_height, up[i][k])
                    count += min_height
                    k -= 1 
                    
                
        return count 
        
        
                
            
                
                    
        
                
                


class Solution:
    def numSubmat(self, mat: List[List[int]]) -> int:
        # Make H matrix
        H = mat 
        for i in range(1, len(mat)):
            for j in range(len(mat[0])):
                if H[i][j] == 0: continue
                H[i][j] = H[i-1][j] + 1
        
        #count rect with bottom left corner i,j
        total = 0
        for i in range(len(H)):
            for j in range(len(H[0])):
                if H[i][j] == 0: continue
                h = H[i][j]
                total += h
                for k in range(j+1, len(H[0])):
                    if H[i][k] == 0: break
                    h = min(H[i][k], h)
                    total += h
        return total


class Solution:
    def numSubmat(self, mat: List[List[int]]) -> int:
        m = len(mat)
        n = len(mat[0])
        
        heights = [0] * n
        
        count = 0
        
        for i in range(m):
            for j in range(n):
                if mat[i][j] == 0:
                    heights[j] = 0
                else:
                    heights[j] += 1
                   

            for j in range(n):
                k = j
                smallest_height = heights[k]
                
                while k > -1 and heights[k] > 0:
                    smallest_height = min(smallest_height, heights[k])
                    count += smallest_height
                    k -= 1

        return count

# O(mn*mn) time and O(1) space
class Solution:
    def numSubmat(self, mat: List[List[int]]) -> int:
        rows = len( mat )
        cols = len( mat[0] )

        \"\"\"
        For each row, determine the number of submatrices of all 1's
        that exist in that row. While moving horizontally along the
        row, count the submatrices that terminate at each location.
        Save the count of submatrices in the variable submatrices.
        \"\"\"
        submatrices = 0
        for r in range( rows ):
            submatrices += mat[r][0]
            for c in range( 1, cols ):
                if mat[r][c]:
                    if c > 0:
                        mat[r][c] = mat[r][c - 1] + 1
                    submatrices += mat[r][c]

        \"\"\"
        At this point we have counted the submatrices that exist
        within a single row. The code below counts the submatrices
        that span multiple rows, then returns the sum of the two
        counts.
        
        Process the above matrix one row at a time. Moving down each
        column, determine the number of submatrices of all 1's that
        start on that row looking left and span multiple rows.  Repeat
        for each row and return the total number of submatrices.

        For each 1 within a row, count the submatrices that contain
        the 1, start on the same row either at or before the 1, and
        span multiple rows. Proceed down the column that contains the 1
        until reaching a 0 or the bottom row of the matrix. While
        proceeding down a column, the width of the submatrices may
        stay the same or gets thinner.
        \"\"\"
        for r in range( rows - 1 ):
            for c in range( cols ):
                if mat[r][c]:
                    row = r + 1
                    submatrix_width = mat[r][c]
                    while row < rows and mat[row][c]:
                        submatrix_width = min( submatrix_width, mat[row][c] )
                        submatrices += submatrix_width
                        row += 1
        return submatrices

class Solution:
    def numSubmat(self, mat: List[List[int]]) -> int:
        M=len(mat)
        N=len(mat[0])
        
        mark=[[0 for _ in range(N)] for _ in range(M)]
        
        for m in range(M):
            for n in range(N):
                if n==0:
                    mark[m][n]=mat[m][n]
                else:
                    mark[m][n]=mark[m][n-1]+1 if mat[m][n]==1 else 0
        res=0          
        for bottom in range(M):
            for right in range(N):
                Min=mark[bottom][right]
                for upper in range(bottom+1)[::-1]:      
                    Min=min(Min,mark[upper][right])
                    if Min==0:
                        break
                    res+=Min
                    
        return res
                    
        
#     ## Brute Force w/ Pruning O(N^2*M^2)
#     def numSubmat(self, mat: List[List[int]]) -> int:
#         M=len(mat)
#         N=len(mat[0])
#         res=0       
        
#         for top in range(M):
#             for left in range(N):
#                 bound=N ## to bound the right pointer
#                 for bottom in range(top,M):                    
#                     right=left
#                     while right<bound:
#                         if mat[bottom][right]==1:
#                             res+=1
#                             right+=1
#                         else:
#                             bound=right
#                             break
#         return res                  
                        
                        
                    
                


class Solution:
    def numSubmat(self, mat: List[List[int]]) -> int:
        

        rows = len( mat )
        cols = len( mat[0] )


        for r in range( rows ):
            for c in range( 1, cols ):
                if mat[r][c]:
                    if c > 0:
                        mat[r][c] = mat[r][c - 1] + 1


        submatrices = 0
        for r in range( rows ):
            for c in range( cols ):
                if mat[r][c]:
                    row = r
                    submatrix_width = mat[r][c]
                    while row < rows and mat[row][c]:
                        submatrix_width = min( submatrix_width, mat[row][c] )
                        submatrices += submatrix_width
                        row += 1
        return submatrices


class Solution:
    def numSubmat(self, mat: List[List[int]]) -> int:
        

        rows = len( mat )
        cols = len( mat[0] )


        for r in range( rows ):
            for c in range( 1, cols ):
                if mat[r][c]:
                    if c > 0:
                        mat[r][c] = mat[r][c - 1] + 1

        
        submatrices = 0
        for r in range( rows ):
            for c in range( cols ):
                if mat[r][c]:
                    row = r
                    submatrix_width = mat[r][c]
                    while row < rows and mat[row][c]:
                        submatrix_width = min( submatrix_width, mat[row][c] )
                        submatrices += submatrix_width
                        row += 1
        return submatrices


class Solution:
    #TC: O(row*col*row)
    #SC: O(row*col)
    def numSubmat(self, mat: List[List[int]]) -> int:
        nums = [[0]*len(mat[0]) for _ in range(len(mat))]
        for row in range(len(mat)):
            for col in range(len(mat[0])):
                if col == 0:
                    nums[row][col] = mat[row][col]
                else:                
                    if mat[row][col] == 0:
                        nums[row][col] = 0
                    else:
                        nums[row][col] = nums[row][col-1] + 1 
        res = 0        
        for row in range(len(mat)):
            for col in range(len(mat[0])):
                Min = nums[row][col]
                k = row
                while(k>=0):
                    if nums[k][col] == 0:
                        break
                    Min = min(nums[k][col], Min)
                    res += Min
                    k -= 1
        return res

class Solution:
    def numSubmat(self, mat: List[List[int]]) -> int:
        m, n = len(mat), len(mat[0])
        for i in range(m):
            for j in range(n):
                if mat[i][j]:
                    if j > 0:
                        mat[i][j] = mat[i][j - 1] + 1
        # for i in range(m):
        #     for j in range(n):
        #         if mat[i][j]:
        #             if i > 0:
        #                 mat[i][j] = mat[i - 1][j] + 1
                    
        total = 0
        for i in range(m):
            for j in range(n):
                if mat[i][j]:
                    row = i
                    width = mat[i][j]
                    while row < m and mat[row][j]:
                        width = min(width, mat[row][j])
                        total += width
                        row += 1
                        
        return total

class Solution:
    
    def numSubmat(self, mat: List[List[int]]) -> int:
        nums = [[0]*len(mat[0]) for _ in range(len(mat))]
        for row in range(len(mat)):
            for col in range(len(mat[0])):
                if col == 0:
                    nums[row][col] = mat[row][col]
                else:                
                    if mat[row][col] == 0:
                        nums[row][col] = 0
                    else:
                        nums[row][col] = nums[row][col-1] + 1 
        res = 0        
        for row in range(len(mat)):
            for col in range(len(mat[0])):
                Min = nums[row][col]
                k = row
                while(k>=0):
                    if nums[k][col] == 0:
                        break
                    Min = min(nums[k][col], Min)
                    res += Min
                    k -= 1
        return res


class Solution:
    def numSubmat(self, mat: List[List[int]]) -> int:
        if len(mat) == 0:
            return 0
        hist = [0] * len(mat[0])
        res = 0
        for row in mat:
            stack = []
            count = 0
            for i in range(len(row)):
                if row[i]:
                    hist[i] += row[i]
                else:
                    hist[i] = 0
                
                while stack and hist[stack[-1]] > hist[i]:
                    jj = stack.pop()
                    kk = stack[-1] if stack else -1
                    count -= (hist[jj] - hist[i])*(jj - kk)
                
                count += hist[i]
                res += count
                stack.append(i)
        
        return res

class Solution:
    def numSubmat(self, mat: List[List[int]]) -> int:
        n = len(mat)
        m = len(mat[0])
        count = 0
        dp = [[0]*m for _ in range(n)]
        for i in range(n):
            c = 0
            for j in range(m-1, -1, -1):
                if mat[i][j]:
                    c += 1
                else:
                    c = 0
                dp[i][j] = c
        # print(dp)
        for j in range(m):
            # print('j:',j)
            for i in range(n):
                if dp[i][j]:
                    # print('i:',i)
                    min_v = dp[i][j]
                    count += dp[i][j]
                    # print('count:', count)
                    for k in range(i+1,n):
                        # print('k:',k)
                        min_v = min(min_v, dp[k][j])
                        # print('min_v:',min_v)
                        if not min_v: break
                        count+= (k-i+1)*min_v - (k-i)*min_v
                        # print('count:', count)
                    # print()
        return count
                    
                


class Solution:
    def numSubmat(self, mat: List[List[int]]) -> int:
        for j in range(len(mat[0])):
            for i in range(1, len(mat)):
                if mat[i][j] != 0:
                    if mat[i-1][j] != 0:
                        mat[i][j] = mat[i-1][j] + 1
        
        cnt = 0
        for i in range(0, len(mat)):
            for j in range(len(mat[0])):
                min_height = len(mat)
                for k in range(j, -1, -1):
                    if mat[i][k] == 0:
                        break
                    min_height = min(min_height, mat[i][k])
                    cnt += min_height
        
        return cnt

class Solution:
    def numSubmat(self, mat: List[List[int]]) -> int:
        
        for i in range(len(mat)):
            for j in range(1, len(mat[0])):
                if mat[i][j]:
                    mat[i][j] = mat[i][j - 1] + 1
                    
        # for row in mat:
        #    print(row)
        
        count = 0
        
        for i in range(len(mat)):
            for j in range(len(mat[0])):
                if mat[i][j]:
         #           print(i, j, mat[i][j])
                    
                    row = i
                    width = mat[i][j]
                    while row < len(mat) and mat[row][j]:
                        width = min(width, mat[row][j])
                        row += 1
                        count += width
        #                print(width)
        return count

class Solution:
    def numSubmat(self, mat: List[List[int]]) -> int:
        n = len(mat)
        m = len(mat[0])
        count = 0
        for i in range(n):
            c = 0
            for j in range(m-1, -1, -1):
                if mat[i][j]:
                    c += 1
                    mat[i][j] = c
                else:
                    c = 0
                
        for j in range(m):
            for i in range(n):
                if mat[i][j]:
                    min_v = mat[i][j]
                    count += mat[i][j]
                    for k in range(i+1,n):
                        if not mat[k][j]: break
                        min_v = min(min_v, mat[k][j])
                        count+= (k-i+1)*min_v - (k-i)*min_v
        return count
                    
                


class Solution:
    def numSubmat(self, mat: List[List[int]]) -> int:
        n = len(mat)
        m = len(mat[0])
        count = 0
        dp = [[0]*m for _ in range(n)]
        for i in range(n):
            c = 0
            for j in range(m-1, -1, -1):
                if mat[i][j]:
                    c += 1
                else:
                    c = 0
                dp[i][j] = c
        # print(dp)
        for j in range(m):
            # print('j:',j)
            for i in range(n):
                if dp[i][j]:
                    # print('i:',i)
                    min_v = dp[i][j]
                    count += dp[i][j]
                    # print('count:', count)
                    for k in range(i+1,n):
                        # print('k:',k)
                        if not mat[k][j]: break
                        min_v = min(min_v, dp[k][j])
                        # print('min_v:',min_v)
                        count+= (k-i+1)*min_v - (k-i)*min_v
                        # print('count:', count)
                    # print()
        return count
                    
                


class Solution:
    def numSubmat(self, mat: List[List[int]]) -> int:
        n = len(mat)
        m = len(mat[0])
        count = 0
        # dp = [[0]*m for _ in range(n)]
        for i in range(n):
            c = 0
            for j in range(m-1, -1, -1):
                if mat[i][j]:
                    c += 1
                    mat[i][j] = c
                else:
                    c = 0
                
        # print(dp)
        for j in range(m):
            # print('j:',j)
            for i in range(n):
                if mat[i][j]:
                    # print('i:',i)
                    min_v = mat[i][j]
                    count += mat[i][j]
                    # print('count:', count)
                    for k in range(i+1,n):
                        # print('k:',k)
                        if not mat[k][j]: break
                        min_v = min(min_v, mat[k][j])
                        # print('min_v:',min_v)
                        count+= (k-i+1)*min_v - (k-i)*min_v
                        # print('count:', count)
                    # print()
        return count
                    
                


class Solution:
    def numSubmat(self, mat: List[List[int]]) -> int:
        
#         rows = len( mat )
#         cols = len( mat[0] )

#         for r in range( rows ):
#             for c in range( 1, cols ):
#                 if mat[r][c]:
#                     if c > 0:
#                         mat[r][c] = mat[r][c - 1] + 1

#         submatrices = 0
#         for r in range( rows ):
#             for c in range( cols ):
#                 if mat[r][c]:
#                     row = r
#                     submatrix_width = mat[r][c]
#                     while row < rows and mat[row][c]:
#                         submatrix_width = min( submatrix_width, mat[row][c] )
#                         submatrices += submatrix_width
#                         row += 1
#         return submatrices
        
        
        res = 0
        
        for i in range(len(mat)):
            for j in range(1, len(mat[0])):
                if mat[i][j]:
                    if j>0:
                        mat[i][j] = mat[i][j-1] +1
        
        for i in range(len(mat)):
            for j in range(len(mat[0])):
                if mat[i][j]:
                    r = i
                    wid = mat[i][j]
                    while r<len(mat) and mat[r][j]:
                        wid = min(mat[r][j],wid)
                        res += wid
                        r +=1
        return res

class Solution:
    def numSubmat(self, mat: List[List[int]]) -> int:
        
        
        
        # my solution ... 464 ms ... 70 % ... 15.5 MB ... 0 %
        #  time: O(n*m*min(n,m))
        # space: O(n*m)
        
        def func(i, j):
            res = 0
            height = float('inf')
            for jj in range(j, -1, -1):
                height = min(height, cnt[i][jj][1])
                if not height:
                    break
                res += height  # 【(i,jj)为左下角，(i,j)为右下角】的矩形个数
            return res
        
        n, m = len(mat), len(mat[0])
        cnt = [[0]*m for _ in range(n)]
        tot = 0
        for i in range(n):
            for j in range(m):
                if not mat[i][j]:
                    cnt[i][j] = (0, 0)  # cnt[i][j] = (ij及左侧1的个数，ij及上方1的个数)
                else:
                    lft = cnt[i][j-1][0] + 1 if j > 0 else 1
                    top = cnt[i-1][j][1] + 1 if i > 0 else 1
                    cnt[i][j] = (lft, top)
                    tot += func(i, j)
        return tot
        
        


class Solution:
    def numSubmat(self, mat: List[List[int]]) -> int:
        ## https://leetcode.com/problems/count-submatrices-with-all-ones/discuss/720265/Java-Detailed-Explanation-From-O(MNM)-to-O(MN)-by-using-Stack
        ## similar idea: 84. Largest Rectangle in Histogram
        ## process row by row
        def helper(h): ## h is the effective cummulative height at position j
            res = 0 
            st = []
            ## store number of rectangle (all ones) with h[i] as bottom-right corner
            sum_ = [0] * len(h) 
            for i in range(len(h)):
                ## pop those higher blocks, since it will not give more rectangles
                while len(st)>0 and h[st[-1]]>=h[i]:
                    st.pop()
                
                ## if we have a lower block in the stack
                if len(st)>0:
                    left_bound = st[-1]
                    ## Extend the previous rectangular at index \"left_bound\". 
                    ## every rectangle that has left_bound as bottom-right corner can be extended to current index
                    ## thus sum_[i] += sum_[left_bound] 
                    ## add rectangles that have height same as h[left_bound]
                    sum_[i] += sum_[left_bound] 
                    sum_[i] += h[i] * (i-left_bound) ## add rectangles with height h[i] 
                                                     ## width =  (i - left_bound)
                else:
                    sum_[i] = h[i] * (i+1) # left_bound = -1 
                
                st.append(i)
                
            return sum(sum_)
        
        res = 0
        h = [0] * len(mat[0])
        for i in range(len(mat)):
            for j in range(len(mat[0])):
                if mat[i][j] == 1:
                    h[j] += 1
                else:
                    h[j] = 0 
                    
            res += helper(h)
        return res
                
        


class Solution:
    def numSubmat(self, mat: List[List[int]]) -> int:
        n = len(mat)
        m = len(mat[0])
        # for x in mat: print(x) 
        count = 0
        for i in range(n):
            c = 0
            for j in range(m-1, -1, -1):
                if mat[i][j]:
                    c += 1
                    mat[i][j] = c
                else:
                    c = 0
        
        for j in range(m):
            for i in range(n):
                if mat[i][j]:
                    min_v = mat[i][j]
                    count += mat[i][j]
                    for k in range(i+1,n):
                        if not mat[k][j]: break
                        min_v = min(min_v, mat[k][j])
                        count+= (k-i+1)*min_v - (k-i)*min_v
        return count
                    
                


class Solution:
    def numSubmat(self, g: List[List[int]]) -> int:
        # traverse grid, if value is \"1\"
        # record increasing \"width\" from left, or clear to zero on grid == 0
        # across rows, submatrix count is:
        # current width + min(curr width, prev width) + ...
        # stepping down till grid boundary or g[r][c] zero value
        # O(MN * N) time, O(1) space

        rows, cols, res = len(g), len(g[0]), 0

        for r in range(rows):
            width = 0
            for c in range(cols):
                # increment row width from left
                if g[r][c]:
                    width += 1
                    g[r][c] = width
                else:
                    width = 0

                # account for current row submatrix count
                res += width

                # account for previous row submatrix count
                row, prev_width = r, width
                while row > 0 and g[row-1][c]:
                    prev_width = min(prev_width, g[row-1][c])
                    res = res + prev_width
                    row -= 1

        return res

class Solution:
    def numSubmat(self, mat: List[List[int]]) -> int:
        row = len(mat)
        col = len(mat[0])
        
        res = 0
        dp = [[0 for _ in range(col)] for _ in range(row)]
        
        for i in range(row):
            for j in range(col-1, -1, -1):
                if mat[i][j] == 1:
                    dp[i][j] = mat[i][j]
                    if j < col-1:
                        dp[i][j] += dp[i][j+1]
        print(dp)                       
        for i in range(row):
            for j in range(col):
                if mat[i][j] == 1:
                    curr_row = i
                    width = dp[curr_row][j]
                    while curr_row < row and dp[curr_row][j] >= 1:
                        width = min(dp[curr_row][j], width)
                        res += width
                        curr_row +=1
        return res
                        
                                             


class Solution:
    def numSubmat(self, mat) -> int:
        m, n = len(mat), len(mat[0])
        self.count = 0
        
        for i in range(m):
            for j in range(n):
                if mat[i][j]:
                    if j > 0:
                        mat[i][j] += mat[i][j-1]
        
        for i in range(m):
            for j in range(n):
                if mat[i][j]:
                    row = i 
                    submatrix_width = mat[i][j]
                    while row < m and mat[row][j]:
                        submatrix_width = min(submatrix_width, mat[row][j])
                        self.count += submatrix_width
                        row += 1
        return self.count

class Solution:
    def numSubmat(self, mat: List[List[int]]) -> int:
        
        # for each row, calculate how many matrices can you build with all ones
        
        # then for each cell keep increasing height and taking minimum and adding its count
        
        if not mat:
            return 0
        
        for row in range(len(mat)):
            for col in range(len(mat[0])):
                count = 0
                if mat[row][col] == 1:
                    for index in range(col,len(mat[0])):
                        if mat[row][index]:
                            count +=1
                        else:
                            break
                            
                mat[row][col] = count
        
        # now we take each cell and increase height one by one and keep adding to the
        # final answer
        ans = 0
        for row in range(len(mat)):
            for col in range(len(mat[0])):
                count = 0
                if mat[row][col]: # atleast some matrix starts at this point
                    min_width = mat[row][col]
                    for index in range(row,len(mat)):
                        if not mat[index][col]: # can't expand matrix anymore
                            break 
                        min_width = min(min_width, mat[index][col])
                        count += min_width
                ans += count
                
        return ans
                    #keep increasing 
        
        
        
        
                


class Solution:
    def numSubmat(self, mat: List[List[int]]) -> int:
        rows = len(mat);
        cols = len(mat[0]);
        dp = [[0 for _ in range(cols)] for _ in range(rows)];
        for r in range(rows):
            for c in range(cols):
                if c == 0:
                    dp[r][c] = mat[r][c];
                else:
                    if mat[r][c] == 1:
                        dp[r][c] = dp[r][c-1] + 1;
        count = 0;
        for r in range(rows):
            for c in range(cols):
                min_width = dp[r][c];
                for h_idx in range(r, -1, -1):
                    min_width = min(min_width, dp[h_idx][c]);
                    count += min_width
                    if min_width == 0:
                        break
        return count

class Solution:
    def numSubmat(self, mat: List[List[int]]) -> int:
        
        dp = [[0 for _ in range(len(mat[0]))] for _ in range(len(mat))]
        
        for i in range(len(mat)):
            for j in range(len(mat[0]) - 1, -1, -1):
                if mat[i][j] == 1:
                    dp[i][j] = 1 + (dp[i][j + 1] if j < len(mat[0]) - 1 else 0)
        
        ans = 0
        for j in range(len(mat[0])):
            for i in range(len(mat)):
                t = float('inf')
                
                for k in range(i, len(mat)):
                    t = min(t, dp[k][j])
                    
                    if t == 0:
                        break
                    else:
                        ans += t
        
        return ans


class Solution:
    def numSubmat(self, mat: List[List[int]]) -> int:
        m = len(mat)
        if m == 0:
            return 0
        
        n = len(mat[0])
        if n == 0:
            return 0
        temp = [0, 0]
        count = [[[0]*2 for l in range(n)] for _ in range(m)]
        res = 0
        for i in range(m):
            for j in range(n):
                if i == 0 and j == 0:
                    res += mat[i][j]
                    count[i][j][0] = mat[i][j]
                    count[i][j][1] = mat[i][j]
                    continue
                elif i == 0 and mat[i][j]:
                    count[i][j][1] += count[i][j-1][1]+1
                    res += count[i][j][1]
                    count[i][j][0] = mat[i][j]
                elif j == 0 and mat[i][j]:
                    count[i][j][0] += count[i-1][j][0]+1
                    res += count[i][j][0]
                    count[i][j][1] = mat[i][j]
                elif mat[i][j]:
                    res += 1
                    count[i][j][1] += count[i][j-1][1]+1
                    count[i][j][0] += count[i-1][j][0]+1
                    if count[i][j-1][1]:
                        res += count[i][j-1][1]
                    if count[i-1][j][0]:
                        res += count[i-1][j][0]
                    findmin = count[i][j][0]
                    for k in range(1, count[i][j][1]):
                        findmin = min(findmin, count[i][j-k][0])
                    # if count[i][j][0] > 1 and count[i][j][1] > 1 and count[i-1][j-1][0] >= 1:
                    #     # count[i][j][2] = 
                    #     # res += min(count[i][j][0], count[i][j][1])-1
                        res += findmin-1
                    
                # print(i, j, res)
        # print(count)
        return res

from functools import lru_cache
from itertools import product


class Solution:
    def numSubmat(self, mat: List[List[int]]) -> int:
        R, C = len(mat), len(mat[0])

        @lru_cache(None)
        def leftsum(i, j):
            if j < 0 or mat[i][j] == 0:
                return 0
            return 1 + leftsum(i, j - 1)
        
        ret = 0
        
        for bottom, j in product(list(range(R)), list(range(C))):
            width = j + 1
            for top in range(bottom, -1, -1):
                width = min(leftsum(top, j), width)
                if width == 0:
                    break
                ret += width

        return ret


class Solution:
    def numSubmat(self, mat: List[List[int]]) -> int:
        if not mat:
            return 0
    
        for i in range(len(mat)):
            for j in range(1, len(mat[0])):
                mat[i][j] = 1 + mat[i][j-1] if mat[i][j] !=0 else 0

        for j in range(len(mat[0])):
            # keep a mono increasing stack
            # if current num >= prv num-> curr num + prev mat[i-1][j]
            # if current num < prv num -> clean stack

            stack = [(-1, -1)] # index, value
            for i in range(len(mat)):
                while stack and mat[i][j] < stack[-1][1]:
                    stack.pop()
                stack.append((i, mat[i][j]))
                mat[i][j] = mat[i][j] * (i - stack[-2][0]) + (mat[stack[-2][0]][j] if stack[-2][0] != -1 else 0)

        return sum([sum(arr) for arr in mat])

class Solution:
    def numSubmat(self, mat: List[List[int]]) -> int:
        count = 0
        r = len(mat)
        c = len(mat[0])
        for i in range(r):
            for j in range(c-2, -1, -1):
                if mat[i][j] == 1:
                    mat[i][j] += mat[i][j+1]
        for i in range(r):
            for j in range(c):
                minm = mat[i][j]
                d = i
                while d < r and mat[d][j] != 0:
                    minm = min(minm, mat[d][j])
                    count += minm
                    d += 1
        return count

class Solution:
    def numSubmat(self, mat: List[List[int]]) -> int:
        m = len(mat)
        if m == 0: return 0
        n = len(mat[0])
        if n == 0: return 0
        dp = [[0] * n for _ in range(m)]
        for i in range(m):
            for j in range(n):
                if j == 0:
                    dp[i][j] = mat[i][j]
                else:
                    if mat[i][j] == 1:
                        dp[i][j] = dp[i][j-1] + 1
        result = 0
        for i in range(m):
            for j in range(n):
                min_width = dp[i][j]
                for row_idx in range(i,-1,-1):
                    min_width = min(min_width, dp[row_idx][j])
                    result += min_width
                    if min_width == 0:
                        break
        return result


class Solution:
    def numSubmat(self, mat: List[List[int]]) -> int:
        if not mat: 
            return 0
        rows = len(mat)
        cols = len(mat[0])
        n = 0
        
        for top in range(rows):
            for left in range(cols):
                bottom = rows
                for right in range(left, cols):
                    scan = top
                    while scan < bottom and mat[scan][right]: scan += 1
                    bottom = scan
                    n += bottom - top
                    if bottom == top: break
        return n

class Solution:
    def numSubmat(self, mat: List[List[int]]) -> int:
        if not mat: return 0
        rows = len(mat)
        cols = len(mat[0])
        n = 0
        for top in range(rows):
            for left in range(cols):
                bottom = rows
                for right in range(left, cols):
                    scan = top
                    while scan < bottom and mat[scan][right]: scan += 1
                    bottom = scan
                    n += bottom - top
                    if bottom == top: break
        return n


class Solution:
    def numSubmat(self, mat: List[List[int]]) -> int:
        n = len(mat)
        m = len(mat[0])
        width = [[0 for _ in range(m)] for _ in range(n)]
        for i in range(n):
            width[i][0] = mat[i][0]
        for i in range(n):
            for j in range(1,m):
                if(mat[i][j]!=0):
                    width[i][j] = width[i][j-1]+1
        
        
        ans = 0
        for i in range(n):
            for j in range(m):
                if(mat[i][j] != 0):
                    min_width = width[i][j]                    
                    for new_i in range(i,-1,-1):
                        if(mat[new_i][j] == 0):
                            break
                        min_width = min(min_width, width[new_i][j])
                        ans += min_width
        return ans
                        
                        
                
        


class Solution:
    def numSubmat(self, mat: List[List[int]]) -> int:
        m, n = len(mat), len(mat[0])
        for i in range(1, m):
            for j in range(n):
                if mat[i][j]:
                    mat[i][j] += mat[i - 1][j]
        result = 0
        for i in range(m):
            for k in range(i, m):
                height = k - i + 1
                width = 0
                for j in range(n):
                    if mat[k][j] >= height:
                        width += 1
                        result += width
                    else:
                        width = 0
        return result

def no_of_submat(r, c):
    return r*c
    
    
class Solution:
    def numSubmat(self, mat: List[List[int]]) -> int:
        n = len(mat)
        m = len(mat[0])
        count = 0
        dp = [[0]*m for _ in range(n)]
        for i in range(n):
            c = 0
            for j in range(m-1, -1, -1):
                if mat[i][j]:
                    c += 1
                else:
                    c = 0
                dp[i][j] = c
        # print(dp)
        for j in range(m):
            # print('j:',j)
            for i in range(n):
                if dp[i][j]:
                    # print('i:',i)
                    min_v = dp[i][j]
                    count += no_of_submat(1,dp[i][j])
                    # print('count:', count)
                    for k in range(i+1,n):
                        # print('k:',k)
                        min_v = min(min_v, dp[k][j])
                        # print('min_v:',min_v)
                        if not min_v: break
                        count+= no_of_submat(k-i+1, min_v)-no_of_submat(k-i, min_v)
                        # print('count:', count)
                    # print()
        return count
                    
                


class Solution:
    def numSubmat(self, mat: List[List[int]]) -> int:
        if not mat: return 0
        
        m, n = len(mat), len(mat[0])
        
        count = 0
        for i in range(m):
            for j in range(n):
                if mat[i][j] == 1:
                    count += 1
                    up, left = i - 1, j - 1
                    
                    while up >= 0 and mat[up][j] == 1: up -= 1
                    count += i - up - 1
                    
                    while left >= 0 and mat[i][left] == 1: left -= 1
                    count += j - left - 1
                    
                    k = i - 1
                    while k > up:
                        l = j - 1
                        if mat[k][l] == 0: break
                        while l > left:
                            if mat[k][l] == 1: 
                                count += 1
                                l -= 1
                            else: 
                                left = l
                                break
                        k -= 1
        return count

class Solution:
    def numSubmat(self, mat: List[List[int]]) -> int:
        for i in range(len(mat)):
            for j in range(len(mat[0])):
                if not mat[i][j]:
                    continue
                mat[i][j] += mat[i-1][j] if i-1 >= 0 else 0
        # count submatrices with all 1s with bottom right corner at (i,j)
        ret = 0
        for i in range(len(mat)):
            row = mat[i]
            stack = []
            tot = 0
            for j in range(len(row)):
                ths = 1
                while stack and stack[-1][0] >= row[j]:
                    popped = stack.pop()
                    tot -= popped[0] * popped[1]
                    ths += popped[1]
                stack.append([row[j], ths])
                tot += ths * row[j]
                ret += tot
        return ret

class Solution:
    def numSubmat(self, mat: List[List[int]]) -> int:
        dph = [[0 for j in range(len(mat[0])+1)] for i in range(len(mat)+1)]
        dpv = [[0 for j in range(len(mat[0])+1)] for i in range(len(mat)+1)]
        dps = [[[] for j in range(len(mat[0])+1)] for i in range(len(mat)+1)]
        
        counts = 0
        for i in range(1,len(mat)+1):
            for j in range(1,len(mat[0])+1):
                if mat[i-1][j-1]==1:
                    dpv[i][j] = dpv[i-1][j]+1
                    dph[i][j] = dph[i][j-1]+1
                    
                    if dpv[i][j]-1>dpv[i-1][j-1]:
                        tmp = collections.deque([dph[i][j]])
                        for k in range(dpv[i][j]-1):
                            if k<dpv[i-1][j-1]:
                                tmp.append(min(dps[i-1][j-1][k]+1,dph[i][j]))
                            else:
                                tmp.append(1)
                    else:
                        tmp = collections.deque([dph[i][j]])
                        for k in range(dpv[i][j]-1):
                            tmp.append(min(dps[i-1][j-1][k]+1,dph[i][j]))
                    dps[i][j] = tmp
                    counts += sum(tmp)
                    
                    
        print(dps)
        return counts

class Solution:
    def numSubmat(self, mat: List[List[int]]) -> int:
        m = len(mat)
        n = len(mat[0])
        dp = [[mat[i][j] for j in range(n)] for i in range(m)]
        for i in range(m):
            for j in range(n-2, -1, -1):
                if mat[i][j] == 1:
                    dp[i][j] = dp[i][j+1] + 1
        # for row in dp:
        #     print(row)
        res = 0
        for i in range(m):
            for j in range(n):
                k = i
                mn = dp[i][j]
                while k < m and dp[k][j] != 0:
                    mn = min(mn, dp[k][j])
                    res += mn
                    k += 1
        return res

class Solution:
#     def numSubmat(self, mat: List[List[int]]) -> int:
#         result = 0
#         for i in range(len(mat)):
#             for j in range(len(mat[i])):
#                 if mat[i][j] == 1:
#                     prev_row_width = -1
#                     for row in range(i, len(mat)):
#                         for col in range(j, len(mat[i])):
#                             if mat[row][col] == 1 and (prev_row_width == -1 or col - j + 1 <= prev_row_width):
#                                 result += 1
#                                 # print(\"Prev Width:\", prev_row_width)
#                                 # print(\"Current Width:\", col - j + 1)
#                                 # print(\"Rectangle with coordinates ({}, {}) and ({}, {})\".format(i, j, row, col))
#                             else:
#                                 prev_row_width = col - j
#                                 break
                                    
                        
#         return result

#     def numSubmat(self, mat: List[List[int]]) -> int:
#         result = 0
#         n = len(mat)
#         m = len(mat[0])
#         consecutive_ones = [[0] * m for _ in range(n)]
        
#         for i in range(n):
#             curr_ones = 0
#             for j in range(m - 1, -1, -1):
#                 if mat[i][j] == 1:
#                     curr_ones += 1
#                 else:
#                     curr_ones = 0
#                 consecutive_ones[i][j] = curr_ones
        
#         # print(consecutive_ones)
        
#         for i in range(n):
#             for j in range(m):
#                 if mat[i][j] == 1:
#                     prev_row_width = float('inf')
#                     for row in range(i, n):
#                         curr_width = consecutive_ones[row][j]
#                         # print(\"Prev Width:\", prev_row_width)
#                         # print(\"Current Width:\",curr_width)

#                         if curr_width == 0:
#                             break
                        
#                         # print(\"Rectangle with coordinates ({}, {}) and ({}, {})\".format(i, j, row, j + curr_width - 1))
#                         result += min(prev_row_width, curr_width)
#                         prev_row_width = min(prev_row_width, curr_width)
                        
#         return result

    def numSubmat(self, mat: List[List[int]]) -> int:
        result = 0
        n = len(mat)
        m = len(mat[0])
        consecutive_ones = [[0]*m for _ in range(n)]
        overall_ones = []
        
        for i in range(n):
            c = 0
            for j in range(m - 1, -1, -1):
                if mat[i][j] == 1:
                    c += 1
                    overall_ones.append((i, j))
                else:
                    c = 0
                consecutive_ones[i][j] = c
                
        while len(overall_ones) != 0:
            leftmost_point = overall_ones.pop()
            i = leftmost_point[0]
            j = leftmost_point[1]
            
            prev_row_width = float('inf')
            for row in range(i, n):
                curr_width = consecutive_ones[row][j]
                
                if curr_width == 0:
                    break
                
                result += min(prev_row_width, curr_width)
                prev_row_width = min(prev_row_width, curr_width)
        
                    
        return result
                
                
        
        
        


class Solution:
    def numSubmat(self, mat: List[List[int]]) -> int:
        rows = len(mat)
        cols = len(mat[0])
        submatrices = 0
        for r in range(rows):
            submatrices += mat[r][0]
            for c in range(1,cols):
                if mat[r][c] != 0:
                    if c > 0:
                        mat[r][c] = mat[r][c - 1] + 1
                    submatrices += mat[r][c]
            
                    
               
        for r in range(rows - 1):
            for c in range(cols):
                if mat[r][c] != 0:
                    row = r + 1
                    submatrix_width = mat[r][c]
                    while row < rows and mat[row][c] != 0:
                        submatrix_width = min(submatrix_width,mat[row][c])
                        
                        submatrices += submatrix_width
                        row += 1
        return submatrices

class Solution:
    def numSubmat(self, mat: List[List[int]]) -> int:
        m = len(mat)
        n = len(mat[0])

        for i in range(m):
            for j in reversed(range(n-1)):
                if mat[i][j] == 1:
                    mat[i][j] = mat[i][j+1] + 1               

        def countSubmat(i, j):
            top = i
            left = j
            bound = n
            counter = 0
            while i < m and mat[i][j] > 0:
                counter += min(bound, mat[i][j])
                bound = min(bound, mat[i][j])
                i += 1
            return counter
        
        total = 0
        for i in range(m):
            for j in range(n):
                if mat[i][j] > 0:
                    total += countSubmat(i, j)
        
        return total

class Solution:
    def get_matrix_cnt(self, cur_row_height):
        res = 0
        for i, polm in enumerate(cur_row_height):
            
            if polm > 0:
                for cur_height in range(1, polm+1):
                    res += 1
                    cur_index = i+1
                    while cur_index < len(cur_row_height) and cur_row_height[cur_index] >= cur_height:
                        res +=1
                        cur_index += 1
        return res
                    
        
    def numSubmat(self, mat: List[List[int]]) -> int:
        
        m = len(mat)
        n = len(mat[0])
        
        cur_row_height = [0] * n
        total = 0
        for row in range(m):
            # get cumulated height based on current row
            for col in range(n):
                if mat[row][col] == 0:
                    cur_row_height[col] = 0
                else:
                    cur_row_height[col] += 1
            
            #print(cur_row_height)
            cur_cnt = self.get_matrix_cnt(cur_row_height)
            total += cur_cnt
            #print(cur_cnt)
        return total

class Solution:
    def numSubmat(self, mat: List[List[int]]) -> int:
        M, N = len(mat), len(mat[0])

        def count_submatrices(a, b):
            count, bound = 0, N

            for i in range(a, M):
                y = b
                while y < bound:
                    if mat[i][y]:
                        count += 1
                    else:
                        bound = y
                    y += 1

                # bound is the boundary of col, if mat[a][b] == 0, means top-left cornor is 0, we won't have any
                # submatrics with all 1's, so return directly
                if bound == b:
                    return count
            return count

        count = 0
        for i in range(M):
            for j in range(N):
                count += count_submatrices(i, j)
        return count




class Solution:
    def numSubmat(self, mat: List[List[int]]) -> int:
        res, lr, lc = 0, len(mat), len(mat[0]) if mat else 0
        for i in range(lr):
            for j in range(lc):
                if mat[i][j]:
                    cur, x, limit = 0, i, lc
                    while x < lr:
                        y = j
                        if not mat[x][y]:
                            break
                        while y < limit:
                            if not mat[x][y]:
                                limit = y
                                break
                            cur, y = cur + 1, y + 1
                        x += 1
                    res += cur
        return res


class Solution:
    def numSubmat(self, mat: List[List[int]]) -> int:
        m = len(mat)
        if m == 0: return 0
        n = len(mat[0])
        if n == 0: return 0
        
        a = [None for _ in range(m)]
        for i in range(m):
            a[i] = []
            for j in range(n):
                a[i].append([0, 0])
        
        for i in range(m):
            for j in range(n-1, -1, -1):
                if i == n-1:
                    a[i][j][0] = 1 if mat[i][j] == 1 else 0
                else:
                    a[i][j][0] = 1 + a[i-1][j][0] if mat[i][j] == 1 else 0
        
        for j in range(n):
            for i in range(m):
                if i == 0:
                    a[i][j][1] = 1 if mat[i][j] == 1 else 0
                else:
                    a[i][j][1] = 1 + a[i-1][j][1] if mat[i][j] == 1 else 0
        
        ans = 0
        for i in range(m):
            j = 0
            while j < n:
                if mat[i][j] == 0:
                    j += 1
                else:
                    minH = a[i][j][1]
                    k = j
                    while k < n and mat[i][k] == 1:
                        minH = min(minH, a[i][k][1])
                        ans += minH
                        k += 1
                    j += 1
        return ans
                    


class Solution:
    def numSubmat(self, mat: List[List[int]]) -> int:
        n = len(mat)
        m = len(mat[0])
        res = 0
        for i in  range(n):
            for j in range(m):
                if mat[i][j]:
                    if j: mat[i][j] += mat[i][j-1]
                    width = mat[i][j]
                    k=i
                    while k>=0 and mat[k][j]>0: 
                        width = min(width, mat[k][j])
                        res += width
                        k -= 1
                    
        return res