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:\n    def numSubmat(self, mat: List[List[int]]) -> int:\n        n, m = len(mat), len(mat[0])\n        heights = [0] * m\n        res = 0\n        for i in range(0, n):\n            stack = []\n            count = 0\n            for j in range(0, m):\n                if mat[i][j] == 1:\n                    heights[j] += 1\n                else:\n                    heights[j] = 0\n            for index, height in enumerate(heights):\n                while stack and height < heights[stack[-1]]:\n                    curr = stack.pop()\n                    left = stack[-1] if stack else -1\n                    count -= (heights[curr] - height) * (curr - left)\n                count += height\n                res += count\n                stack.append(index)\n        return res\n            \n", "class Solution:\n    def numSubmat(self, matrix):\n        m, n = len(matrix), len(matrix[0])\n        res = 0\n        heights = [0] * (n + 1)\n        for x in range(m):\n            stack = []\n            dp = [0] * (n + 1)\n            for y in range(n):\n                if matrix[x][y] == 1:\n                    heights[y] = heights[y] + 1\n                else:\n                    heights[y] = 0\n            for right in range(n + 1):\n                while stack and heights[right] <= heights[stack[-1]]:\n                    cur = stack.pop()\n                if stack:\n                    left = stack[-1]\n                    dp[right] = dp[left] + heights[right] * (right - left) \n                else:\n                    left = -1\n                    dp[right] = heights[right] * (right - left) \n                stack.append(right)\n            res += sum(dp)\n        return res", "\nclass Solution:\n    def numSubmat(self, mat):\n\n        if not mat:\n            return 0\n\n        for i in range(len(mat)):\n            for j in range(1, len(mat[0])):\n                mat[i][j] = 1 + mat[i][j-1] if mat[i][j] !=0 else 0\n\n        for j in range(len(mat[0])):\n            stack = [(-1, -1)] # index, value\n            for i in range(len(mat)):\n                while stack and mat[i][j] < stack[-1][1]:\n                    stack.pop()\n                stack.append((i, mat[i][j]))\n                mat[i][j] = mat[i][j] * (i - stack[-2][0]) + (mat[stack[-2][0]][j] if stack[-2][0] != -1 else 0)\n\n        return sum([sum(arr) for arr in mat])", "class Solution:\n    def numSubmat(self, mat: List[List[int]]) -> int:\n        # udpate mat to histogram\n        row = len(mat)\n        col = len(mat[0])\n        for j in range(col):\n            for i in range(1, row):\n                mat[i][j] = mat[i - 1][j] + 1 if mat[i][j] == 1 else 0 \n        \n        total = 0\n        for i in range(row):\n            for j in range(col):\n                if mat[i][j] == 0:\n                    continue\n                cur = j\n                delta = 0\n                min_h = float('inf')\n                while cur >= 0 and mat[i][cur] != 0:\n                    cur_h_above = mat[i - 1][cur] if i - 1 >= 0 else 0\n                    min_h = min(min_h, cur_h_above)\n                    delta += (min_h + 1)\n                    cur -= 1\n                total += delta\n        return total", "class Solution:\n    def numSubmat(self, mat: List[List[int]]) -> int:\n        rows = len(mat)\n        columns = len(mat[0])\n        def countSubmat(s_r, s_c):\n            e_r = rows\n            e_c = columns\n            c_r = s_r\n            c_c = s_c\n            count = 0\n            while c_r < e_r:\n                if mat[c_r][s_c] == 0:\n                    break\n                else:\n                    count += 1\n                    c_c = s_c + 1\n                while c_c < e_c:\n                    if mat[c_r][c_c] == 1:\n                        count += 1\n                    else:\n                        e_c = c_c\n                    c_c += 1\n                c_r += 1\n                c_c = s_c\n            return count\n        res = 0\n        for i in range(rows):\n            for j in range(columns):\n                res += countSubmat(i, j)\n        return res\n                    \n            \n", "class Solution:\n    def numSubmat(self, mat: List[List[int]]) -> int:\n        if not mat:\n            return 0\n        m, n = len(mat), len(mat[0])\n        prefix = [[0] * n for _ in range(m)]\n        for i in range(m):\n            for j in range(n - 1, -1, -1):\n                if j == n - 1:\n                    prefix[i][j] = mat[i][j]\n                if mat[i][j] == 0:\n                    continue\n                if j + 1 <= n - 1:\n                    prefix[i][j] = prefix[i][j + 1] + mat[i][j]\n        print(prefix)\n        count =  [[0] * n for _ in range(m)]  \n        for i in range(m):\n            for j in range(n):\n                width = prefix[i][j]\n                res = width\n                for k in range(i + 1, m):\n                    if prefix[k][j] <= width:\n                        width = prefix[k][j]\n                        res += prefix[k][j]\n                    else:\n                        res += width\n                count[i][j] = res\n        print(count)\n        ans = 0\n        for i in range(m):\n            ans += sum(count[i])\n        \n        return ans\n                    \n                    \n                    \n", "class Solution:\n    def numSubmat(self, mat: List[List[int]]) -> int:\n        res = 0\n        m, n = len(mat), len(mat[0])\n        \n        dp = [[0 for j in range(n)] for i in range(m)]\n        # width of contnuous ones in row i and ends at mat[i][j]\n        \n        for i in range(m):\n            for j in range(n):\n                if mat[i][j]:\n                    if j == 0:\n                        dp[i][j] = 1\n                    else:\n                        dp[i][j] = dp[i][j-1] + 1\n        \n        for i in range(m):\n            for j in range(n):\n                if mat[i][j] == 0:\n                    continue\n                row, minwidth = i, float('inf')\n                while row >= 0 and mat[row][j]:\n                    minwidth = min(minwidth, dp[row][j])\n                    res += minwidth\n                    row -= 1\n                    \n        return res", "class Solution:\n    def numSubmat(self, mat: List[List[int]]) -> int:\n        R, C = len(mat), len(mat[0])\n        hist = [[0] * C for _ in range(R)]\n        \n        for r in range(R):\n            for c in range(C):\n                if mat[r][c]:\n                    hist[r][c] = 1 if r == 0 else hist[r-1][c] + 1\n        \n        ret = 0\n        for row in hist:\n            all_stacks = []\n            stack = []\n            for num in row:\n                if num > 0:\n                    stack.append(num)\n                elif stack:\n                    all_stacks.append(stack[::])\n                    stack = []\n            if stack:\n                all_stacks.append(stack)\n            \n            for stack in all_stacks:\n                while stack:\n                    last_h = stack[-1]\n                    minsofar = last_h\n                    for h in stack[::-1]:\n                        minsofar = min(minsofar, h)\n                        ret += minsofar\n                    stack.pop()\n            \n        \n        return ret\n", "class Solution:\n    def numSubmat(self, mat: List[List[int]]) -> int:\n        if not mat: return 0\n        \n        m, n = len(mat), len(mat[0])\n        \n        count = 0\n        for i in range(m):\n            for j in range(n):\n                if mat[i][j] == 1:\n                    count += 1\n                    up, left = i - 1, j - 1\n                    \n                    while up >= 0 and mat[up][j] == 1: up -= 1\n                    count += i - up - 1\n                    \n                    while left >= 0 and mat[i][left] == 1: left -= 1\n                    count += j - left - 1\n                    \n                    print(i, j, up, left)\n                    k = i - 1\n                    while k > up:\n                        l = j - 1\n                        if mat[k][l] == 0: break\n                        while l > left:\n                            if mat[k][l] == 1: \n                                count += 1\n                                l -= 1\n                            else: \n                                left = l\n                                break\n                        k -= 1\n        return count", "class Solution:\n    def numSubmat(self, mat: List[List[int]]) -> int:\n        m, n = len(mat), len(mat[0])\n        res = 0\n        for i in range(len(mat)):\n            for j in range(len(mat[0])):\n                if mat[i][j] == 1: # this could be a top-left\n                    right_edge = n\n                    for res_i in range(i, m):\n                        if mat[res_i][j] == 0:\n                            break\n                        for res_j in range(j, right_edge):\n                            if mat[res_i][res_j] == 1:\n                                res += 1\n                            else:\n                                right_edge = min(right_edge, res_j)\n                                break\n        return res", "from math import floor\nfrom math import ceil\nfrom math import sqrt\nfrom collections import deque\nimport numpy\nfrom _collections import deque\n#from _ast import Num # LC doesn't like this\nfrom heapq import *\nfrom typing import List\nimport random\n\nMOD = int(1e9 + 7)\nBASE = 256\n\n\nclass Solution:\n\n    def numSubmat(self, mat: List[List[int]]) -> int:\n        R = len(mat)\n        if not R:\n            return 0\n        C = len(mat[0])\n\n        ans = [[0 for _ in range(C)] for _ in range(C)]\n\n        cnt = 0\n\n        for i in range(R):\n            nextAns = [[0 for _ in range(C)] for _ in range(C)]\n            last0j = -1\n            for j in range(C):\n                if not mat[i][j]:\n                    last0j = j\n\n                for si in range(last0j + 1, j + 1):\n                    nextAns[j][si] = ans[j][si] + 1\n                    cnt += nextAns[j][si]\n                    #print(cnt, j, si)\n            ans = nextAns\n\n        return cnt\n\n\\\"\\\"\\\"\nS = Solution()\nmat = [[1, 1]]\nmat = [[1, 0, 1], [1, 1, 0], [1, 1, 0]]\nmat = [[0, 1, 1, 0], [0, 1, 1, 1], [1, 1, 1, 0]]\nmat = [[1, 1, 1, 1, 1, 1]]\nmat = [[1, 0, 1], [0, 1, 0], [1, 0, 1]]\nprint(S.numSubmat(mat))\n\\\"\\\"\\\"\n", "class Solution:\n    def numSubmat(self, mat: List[List[int]]) -> int:\n        \n        nrows = len(mat)\n        ncols = len(mat[0])\n        \n        for i in range(nrows):\n            for j in range(ncols):\n                if mat[i][j]:\n                    if j > 0:\n                        mat[i][j] = mat[i][j - 1] + 1\n        \n        cnt = 0\n        \n        for i in range(nrows):\n            for j in range(ncols):\n                if mat[i][j]:\n                    row = i\n                    submatrix_width = mat[i][j]\n                    \n                    while row < nrows and mat[row][j]:\n                        submatrix_width = min(submatrix_width, mat[row][j])\n                        cnt += submatrix_width\n                        row += 1\n        return cnt\n\n\n                \n", "class Solution:\n    def numSubmat(self, mat: List[List[int]]) -> int:\n        rows = len(mat)\n        columns = len(mat[0])\n        count = 0\n        for i in range(rows):\n            for j in range(columns):\n                width = columns\n                for y in range(i, rows):\n                    if mat[y][j] == 0:\n                        break\n                    for x in range(j, width):\n                        if mat[y][x] == 0:\n                            width = x\n                            break\n                        count += 1\n        return count", "\\\"\\\"\\\"\n\u7528increasing monostack\u627e\u5230\u4ee5(i, j)\u7ed3\u5c3e\u7684\u5168\u4e3a1\u7684\u6700\u5927rectangle, \u5c31\u5f88\u5bb9\u6613\u8ba1\u7b97\u4ee5(i, j)\u7ed3\u5c3esubmatrices\u7684\u4e2a\u6570\u4e86.\n\\\"\\\"\\\"\nclass Solution:\n    def numSubmat(self, matrix: List[List[int]]) -> int:\n        m, n = len(matrix), len(matrix[0])\n        for i in range(1, m):\n            for j in range(n):\n                if matrix[i][j] == 1:\n                    matrix[i][j] += matrix[i-1][j]  # construct the histogram \n                \n        res = 0\n        for i in range(m):\n            res += self._histogram(matrix[i])       # helper function return the total cnt of row i\n        return res\n        \n    def _histogram(self, heights):\n        \\\"\\\"\\\"\n        \u7b97\u6cd5\u6838\u5fc3\u662f\uff1a\u4ee5j\u7ed3\u5c3e\u7684submatrices\u7684\u4e2a\u6570\u7b49\u4e8eheights[j] * (j - \u5411\u5de6\u627e\u7b2c\u4e00\u4e2aheight\u5c0f\u4e8eheights[j]\u7684idx)\n        \u7b97\u6cd5\u662f84.Largest-Rectangle-in-Histogram, 85.Maximal-Rectangle. we need maintain an increasing stack\n        \\\"\\\"\\\"\n        cnt = [0 for _ in range(len(heights))]\n        st = []\n        for j, height in enumerate(heights):\n            while len(st) > 0 and st[-1][0] >= height:\n                st.pop()\n                \n            if len(st) == 0:\n                cnt[j] = height * (j + 1)\n            else:\n                cnt[j] = height * (j - st[-1][1]) + cnt[st[-1][1]]\n                \n            st.append((height, j))\n\n        return sum(cnt)", "class Solution:\n    def numSubmat(self, mat: List[List[int]]) -> int:\n        M, N = len(mat), len(mat[0])\n\n        def count_submatrices(a, b):\n            count, bound = 0, N\n\n            for i in range(a,M):\n                y = b\n                while y < bound:\n                    if mat[i][y]:\n                        count += 1\n                    else:\n                        bound = y\n                    y += 1\n            return count\n\n        count = 0\n        for i in range(M):\n            for j in range(N):\n                count += count_submatrices(i, j)\n        return count\n\n\n", "class Solution:\n    def numSubmat(self, mat: List[List[int]]) -> int:\n        m, n = len(mat), len(mat[0])\n        res = 0\n        for j in range(n):\n            for i in range(1, m):\n                if mat[i][j]:\n                    mat[i][j] += mat[i-1][j]\n        print(mat)\n        for j in range(n-1, -1, -1):\n            for i in range(m):\n                if mat[i][j]:\n                    minval = mat[i][j]\n                    for k in range(j - 1, -1, -1):\n                        if mat[i][k] == 0:\n                            break\n                        minval = min(minval, mat[i][k])\n                        mat[i][j] += minval\n                res += mat[i][j]\n        print(mat)\n\n        return res\n", "from functools import lru_cache\n\nclass Solution:\n    def numSubmat(self, mat: List[List[int]]) -> int:\n        \n        n = len(mat)\n        m = len(mat[0])\n        \n        total = 0\n        for i in range(n):\n            for j in range(m):\n                bound = m\n                for k in range(i, n):\n                    l = j\n                    while l < bound:\n                        if mat[k][l]: \n                            total += 1\n                            l += 1\n                        else:\n                            bound = l\n        return total", "class Solution:\n    def numSubmat(self, mat: List[List[int]]) -> int:\n        count = 0\n        for i in range(len(mat)):\n            for j in range(len(mat[i])):\n                if(mat[i][j]==1):\n                    #print('pos 0: ',i, ', ', j)\n                    count += 1\n                    down = 0\n                    right = 0\n                    for x in range(i+1,len(mat)):\n                        if(mat[x][j]!=1):\n                            break\n                        #print(x, ', ',j)\n                        count += 1\n                        down += 1\n                    for x in range(j+1,len(mat[i])):\n                        if(mat[i][x]!=1):\n                            break\n                        #print(i,', ',x)\n                        count += 1\n                        right += 1\n                    if(down>0 and right>0):\n                        for x in range(1,down+1):\n                            for y in range(1,right+1):\n                                if(mat[i+x][j+y]!=1):\n                                    right = y-1\n                                    break\n                                #print(i+x,', ',j+y)\n                                count += 1\n        return(count)\n", "class Solution:\n    def numSubmat(self, mat: List[List[int]]) -> int:\n        m = len(mat)\n        n = len(mat[0])\n        rows = []\n        for row in mat:\n            cur = [0]\n            for x in row:\n                cur.append(cur[-1] + x)\n            rows.append(cur)\n            \n        res = 0\n        for j2 in range(1, n+1):\n            for j1 in range(j2):\n                width = j2 - j1\n                pre_idx = -1\n                cur = 0\n                for i in range(m):\n                    if rows[i][j2] - rows[i][j1] != width:\n                        pre_idx = i\n                    else:\n                        res += i - pre_idx\n        return res\n", "class Solution:\n    def numSubmat(self, mat: List[List[int]]) -> int:\n        M=len(mat)\n        N=len(mat[0])\n        res=0       \n        \n        for top in range(M):\n            for left in range(N):\n                bound=N\n                for bottom in range(top,M):                    \n                    right=left\n                    while right<bound:\n                        if mat[bottom][right]==1:\n                            res+=1\n                            right+=1\n                        else:\n                            bound=right\n                            break\n                            \n\n        return res                  \n                        \n                        \n                    \n                \n", "class Solution:\n    def histogramCount(self, histograms):\n        stack = []\n        count = 0\n        out = 0\n        for i in range(len(histograms)):\n            while len(stack)!= 0 and histograms[i] < histograms[stack[-1]]:\n                j = stack.pop()\n                if len(stack) == 0:\n                    k = -1\n                else:\n                    k = stack[-1]\n                count -= (histograms[j]-histograms[i])*(j-k)\n            count += histograms[i]\n            out += count\n            stack.append(i)\n        return out\n            \n    def numSubmatHard(self, mat: List[List[int]]) -> int:\n        prev = [0]*len(mat[0])\n        out = 0\n        for i in range(len(mat)):\n            for j in range(len(mat[i])):\n                if mat[i][j] == 0:\n                    prev[j] = 0\n                else:\n                    prev[j] += mat[i][j]\n            out += self.histogramCount(prev)\n            print(prev, out)\n        return out\n    \n    def memoization(self, grid, i, j, memo):\n        if i == len(grid) or j == len(grid[0]):\n            return 0, 0, 0\n        if memo[i][j] is not None:\n            return memo[i][j]\n        if grid[i][j] == 0:\n            memo[i][j] = 0, 0, 0\n        else:\n            if i == len(grid)-1:\n                _, col, _ = self.memoization(grid, i, j+1, memo)\n                memo[i][j] = 1, col+1, col+1\n            elif j == len(grid[0])-1:\n                row, _, _ = self.memoization(grid, i+1, j, memo)\n                memo[i][j] = row+1, 1, row+1\n            else:\n                rows, _, _ = self.memoization(grid, i+1, j, memo)\n                prev = rows + 1\n                out = prev\n                k = j+1\n                while k < len(grid[0]) and grid[i][k] != 0:\n                    row, _, _ = self.memoization(grid, i, k, memo)\n                    prev = min(prev, row)\n                    out += prev\n                    k += 1\n                memo[i][j] = rows + 1, k - j, out\n        return memo[i][j]\n    \n    def numSubmat(self, mat: List[List[int]]) -> int:\n        memo = [[None for j in range(len(mat[0]))] for i in range(len(mat))]\n        out = 0\n        for i in range(len(mat)):\n            for j in range(len(mat[0])):\n                _, _, val = self.memoization(mat, i, j, memo)\n                out += val\n        return out", "class Solution:\n    def numSubmat(self, mat: List[List[int]]) -> int:\n        \n        # 1\n        \n        rows= len(mat)-1\n        cols= len(mat[0])-1\n        total=0\n        \n        def find_rects(i,j):\n            local=0\n            imax=rows+1\n            j_cur=j\n            while j_cur<=cols:\n                if mat[i][j_cur]==0:\n                    break\n                i_cur=i\n                while i_cur<imax:\n                    if mat[i_cur][j_cur]==1:\n                        i_cur+=1\n                    else:\n                        break\n                imax=min(i_cur,imax)\n                local+=(imax-i)\n                j_cur+=1\n                \n            return local\n                    \n        \n        \n        for i in range(rows+1):\n            for j in range(cols+1):\n                if mat[i][j]==1:\n                    total+=find_rects(i,j)\n        return total", "class Solution:\n    def numSubmat(self, mat: List[List[int]]) -> int:\n        \n        if not mat or not mat[0]:\n            return 0\n        \n        m = len(mat)\n        n = len(mat[0])\n        dp = [[0]*(n+1) for i in range(m+1)]\n        \n        res = 0\n        for i in range(m):\n            for j in range(n):\n                if mat[i][j] == 1:\n                    # dp only counts num from looking left\n                    dp[i+1][j+1] = dp[i+1][j] + 1\n                    res += dp[i+1][j+1]\n                    \n                    minOnes = dp[i+1][j+1]\n                    k = i-1\n                    while k >=0 and mat[k][j] == 1:\n                        minOnes = min(minOnes, dp[k+1][j+1])\n                        res += minOnes\n                        k -= 1\n                        \n                        \n        return res\n", "class Solution:\n    def numSubmat(self, mat: List[List[int]]) -> int:\n        if not mat:\n            return 0\n        answer = 0\n        row, col = len(mat), len(mat[0])\n        # Get the number of 1's to the right of the current 1\n        # For example:\n        # [1, 0, 1]\n        # [1, 1, 0]\n        # [1, 1, 0] \n        # turns into\n        # [1, 0, 1]\n        # [2, 1, 0]\n        # [2, 1, 0]\n        one_counts = [[0 for _ in range(col)] for _ in range(row)]\n        for r in range(row):\n            counter = 0\n            for c in range(col-1,-1,-1): \n                if mat[r][c] == 1:\n                    counter += 1\n                    one_counts[r][c] = counter\n                else:\n                    counter = 0\n        # Go through each element in the matrix, and if it is == 1, check how many\n        # submatricies with this element as the top leftmost point can we generate \n        for r in range(row):\n            for c in range(col):\n                if mat[r][c] == 1:\n                    min_width = float('inf') \n                    for k in range(r, row):\n                        if mat[k][c] == 1:\n                            min_width = min(min_width, one_counts[k][c])\n                            answer += min_width\n                            continue\n                        break  \n        return answer ", "class Solution:\n    def numSubmat(self, mat: List[List[int]]) -> int:\n        m, n = len(mat), len(mat[0])\n        res = 0\n        dp = [0] * n\n        for r in range(m):\n            stack = []\n            for c in range(n):\n                cnt = 0\n                if mat[r][c]:\n                    if r > 0:\n                        mat[r][c] += mat[r-1][c]\n                    while stack and mat[r][stack[-1]] >= mat[r][c]:\n                        stack.pop()\n                    cnt += (c - (stack[-1] if stack else -1))*mat[r][c]\n                    if stack:\n                        cnt += dp[stack[-1]]\n                stack.append(c)\n                dp[c] = cnt\n                res += cnt\n        return res", "class Solution:\n    def numSubmat(self, mat: List[List[int]]) -> int:\n        rows = len(mat)\n        cols = len(mat[0])\n        # row_matrices[i][j] = num of submatrices in row i that ends in col j\n        row_matrices = [[0] * cols for _ in range(rows)]\n        \n        # Count submatrices for every single row\n        for i in range(rows):\n            row_matrices[i][0] = mat[i][0]\n            for j in range(1, cols):\n                if mat[i][j] == 1:\n                    row_matrices[i][j] = row_matrices[i][j - 1] + 1\n                else:\n                    row_matrices[i][j] = 0\n        \n        result = 0\n        \n        for i in range(rows):\n            for j in range(cols):\n                cur_min = float('inf')\n                # Search upwards row by row\n                for k in range(i, -1, -1):\n                    if mat[k][j] == 0:\n                        break\n                        \n                    # why min():\n                    #   0, 1, 1, 1  r0\n                    #   0, 0, 1, 1  r1\n                    #   0, 1, 1, 1  r2\n                    # the num of matrices will be bottlenecked by the row\n                    # with minimum matrices. In this case, r1.\n                    cur_min = min(cur_min, row_matrices[k][j])\n                    result += cur_min\n                    \n        return result\n", "class Solution:\n    def numSubmat(self, mat: List[List[int]]) -> int:\n        m, n = len(mat), len(mat[0])\n        count = 0\n        for left in range(n):\n            row_sums = [0 for _ in range(m)]\n            for right in range(left, n):\n                consec_count = 0\n                width = right - left + 1\n                for bottom in range(m):\n                    row_sums[bottom] += mat[bottom][right]\n                    if row_sums[bottom] != width:\n                        consec_count = 0\n                    else:\n                        consec_count += 1\n                        count += consec_count\n        return count", "class Solution:\n    \n    \n    def singlePointSubmat(self,mat,x,y):\n        row = len(mat)\n        column = len(mat[0])\n        \n        res = 0\n        \n        #stoplength store the first zero position\\\\\n        \n        stoplength = column - y\n        for r in range(row - x):\n            if mat[x+r][y] == 1:\n                res += 1\n            else:\n                return res\n            for c in range(1,column - y):\n                if c >= stoplength:\n                    break\n                if mat[x+r][y+c] == 1:\n                    res += 1\n                else:\n                    stoplength = c\n        return res\n                    \n    def numSubmat(self, mat: List[List[int]]) -> int:\n        \n        #check validity\n        if len(mat) == 0 or len(mat[0]) == 0:\n            return 0\n        \n        #find border\n        \n        row = len(mat)\n        column = len(mat[0])\n        \n        result = 0\n        \n        for r in range(row):\n            for c in range(column):\n                \n                if mat[r][c] == 1:\n                    result += self.singlePointSubmat(mat,r,c)\n        return result", "\nimport copy\nfrom math import sqrt\nfrom typing import List\nimport numpy\n\nimport sys\n\n\nclass Solution:\n  def numSubmat(self, mat: List[List[int]]) -> int:\n    row = len(mat)\n    col = len(mat[0])\n    height = [0] * col\n    result = 0\n    for i in range(row):\n\n      for j in range(col):\n        if mat[i][j] == 0:\n          height[j] = 0\n        else:\n          height[j] = height[j] + 1\n\n        k = j\n        minvalue = sys.maxsize\n        while k >= 0 and height[k] != 0:\n          minvalue = min(minvalue, height[k])\n          result += minvalue\n          k -= 1\n        pass\n      pass\n    return result", "class Solution:\n    def numSubmat(self, mat: List[List[int]]) -> int:\n        \n        # \u751f\u6210\u76f4\u65b9\u56fehistogram\n        def countOneRow(arr):\n            res = 0\n            l = 0\n            for i in range(len(arr)):\n                if arr[i] == 0:\n                    l = 0\n                else: l = l + 1\n                res += l # \u4ee5\u5f53\u524d\u4e3a\u6700\u53f3\uff0c\u53ef\u4ee5\u5f62\u6210l\u4e2a\u77e9\u5f62\n            return res\n        \n        rows = len(mat)\n        cols = len(mat[0])\n        res = 0\n        for top in range(rows):\n            h = [1] * cols\n            for bottom in range(top, rows):\n                for c in range(cols):\n                    # \u6bcf\u4e00\u884c\u90fd\u8ddftop\u6765merge\uff0c\u56e0\u4e3a\u4e2d\u95f4\u5fc5\u987b\u6240\u6709\u683c\u90fd\u662f1\uff0c\u624d\u80fd\u5f62\u6210\u4e00\u4e2a\u77e9\u5f62\n                    h[c] &= mat[bottom][c]\n                res += countOneRow(h)\n                if not any(h): break\n        return res", "class Solution:\n    def numSubmat(self, mat: List[List[int]]) -> int:\n        \n        # \u751f\u6210\u76f4\u65b9\u56fehistogram\n        def countOneRow(arr):\n            res = 0\n            l = 0\n            for i in range(len(arr)):\n                if arr[i] == 0:\n                    l = 0\n                else: l = l + 1\n                res += l # \u4ee5\u5f53\u524d\u4e3a\u6700\u53f3\uff0c\u53ef\u4ee5\u5f62\u6210l\u4e2a\u77e9\u5f62\n            return res\n        \n        rows = len(mat)\n        cols = len(mat[0])\n        res = 0\n        for top in range(rows):\n            h = [1] * cols\n            l = 0\n            for bottom in range(top, rows):\n                for c in range(cols):\n                    # \u6bcf\u4e00\u884c\u90fd\u8ddftop\u6765merge\uff0c\u56e0\u4e3a\u4e2d\u95f4\u5fc5\u987b\u6240\u6709\u683c\u90fd\u662f1\uff0c\u624d\u80fd\u5f62\u6210\u4e00\u4e2a\u77e9\u5f62\n                    h[c] &= mat[bottom][c]\n                res += countOneRow(h)\n                if not any(h): break\n        return res", "class Solution:\n    def numSubmat(self, mat: List[List[int]]) -> int:\n        m,n = len(mat), len(mat[0])\n\n        \n        def compute(h):\n          res = 0\n          temp = 0 \n          for i in range(len(h)):\n             if h[i] > 0:\n                temp += 1\n             else:\n                temp = 0\n             res += temp\n          return res \n\n        ans = 0 \n        for i in range(m):\n          h = [1]*n \n          for k in range(i,m):\n            for j in range(n):\n                 if mat[k][j] == 0:\n                    h[j] = 0 \n            ans += compute(h)\n        return ans   \n        \n\nclass Solution1:\n    def numSubmat(self, mat: List[List[int]]) -> int:\n        def countonerow(A):\n            res,length = 0,0\n            for i in range(len(A)):\n                length = 0 if A[i] == 0 else length + 1\n                res += length\n            return res \n        \n        def compute_one_row(arr):\n            count = 0\n            length = 0\n            for a in arr:\n                if a == 1:\n                    length += 1\n                else:\n                    length = 0 \n                count += length\n            return count \n        \n        m,n = len(mat), len(mat[0])\n        res = 0\n        for i in range(m):\n            h = [1]*n\n            for j in range(i,m):\n                for k in range(n):\n                    if mat[j][k] == 0:\n                        h[k] = 0 \n                res += compute_one_row(h)\n        return res\n\n\n\n    def numSubmat1(self, mat: List[List[int]]) -> int:\n        m,n,res=len(mat),len(mat[0]),0\n        histogram=[0]*(n+1)\n        for i in range(m):\n            stack,dp=[-1],[0]*(n+1)\n            for j in range(n):\n                histogram[j]=0 if mat[i][j]==0 else histogram[j]+1\n                while histogram[j]<histogram[stack[-1]]: #increasing stack\n                    stack.pop()\n                dp[j]=dp[stack[-1]]+histogram[j]*(j-stack[-1]) # Important!!\n                stack.append(j)\n            res+=sum(dp)\n        return res", "class Solution:\n    def numSubmat(self, a: List[List[int]]) -> int:\n        \n        '''\n            1 0 1\n            1 1 0\n            1 1 0\n            \n            -> row0 ~ row0 -> col0 ~ col2 -> 1 x 1: 2\n            -> row0 ~ row1 -> col0 ~ col2 -> 1 x 2: 1\n            -> row0 ~ row2 -> col0 ~ col2 -> 1 x 3: 1\n            -> row1 ~ row1 -> col0 ~ col2 -> 1 x 1: 2\n            -> row1 ~ row2 -> col0 ~ col2 -> 1 x 2: 2, 2 x 1: 2, 2 x 2 = 1\n            -> row2 ~ row2 -> col0 ~ col2 -> 1 x 1: 2\n            \n            2 + 1 + 1 + 2 + 2 + 2 + 1 + 2\n                = 13                                \n        '''\n        m = len(a)\n        n = len(a[0])\n        \n        def oneDHelper(A):\n            res = 0\n            l = 0\n            for i in range(0, len(A)):\n                if A[i] == 0:\n                    l = 0        \n                else:\n                    l = l + 1        \n                res += l                \n            return res\n\n        count = 0\n        for r1 in range(0, m):            \n            isAll1 = a[r1]            \n            for r2 in range(r1, m):\n                \n                for c in range(0, n):\n                    if a[r2][c] == 0:\n                        isAll1[c] = 0\n                \n                count += oneDHelper(isAll1)\n                                                \n        return count\n                \n                \n                    \n                    \n                    \n                    \n                    \n                \n                \n                \n                          \n", "class Solution:\n    def numSubmat(self, mat: List[List[int]]) -> int:\n        m, n = len(mat), len(mat[0])\n    \n        for i in range(m):\n            for j in range(n):\n                if mat[i][j] and i > 0:\n                    mat[i][j] += mat[i-1][j]\n\n        res = 0          \n        for i in range(m):\n            stack = []\n            cnt = 0\n            for j in range(n):\n                while stack and mat[i][stack[-1]] > mat[i][j]:\n                    tmp = stack.pop()\n                    left = stack[-1] if stack else -1\n                    cnt -= (mat[i][tmp] - mat[i][j]) * (tmp - left)\n                cnt += mat[i][j]\n                res += cnt\n                stack.append(j)\n        return res", "class Solution:\n    def numSubmat(self, mat: List[List[int]]) -> int:\n        m, n = len(mat), len(mat[0])\n        \n        ans = 0\n        for left in range(n):\n            row_sum = [0 for _ in range(m)]\n            for right in range(left, n):\n                consec_count = 0\n                w = right - left + 1\n                for bottom in range(m):\n                    row_sum[bottom] += mat[bottom][right]\n                    if row_sum[bottom] != w:\n                        consec_count = 0\n                    else:\n                        consec_count += 1\n                        ans += consec_count\n        return ans", "class Solution:\n    def countSubMat(self,rowmat:List[int])->int:\n        # count=rowmat[0]\n        # for i in range(1,len(rowmat)):\n        #     rowmat[i]=0 if rowmat[i]==0 else (rowmat[i-1]+rowmat[i])\n        #     count+=rowmat[i]\n        \n        length=0\n        count=0\n        for i in range(len(rowmat)):\n            length=0 if rowmat[i]==0 else (length+1)\n            count+=length\n        return count\n    \n    def numSubmat(self, mat: List[List[int]]) -> int:\n        count=0\n        \n        for m in range(len(mat)):\n            \n            h=[1 for _ in range(len(mat[0]))]\n            for down in range(m,len(mat),1):\n                for n in range(len(mat[0])):\n                    h[n]=h[n]and mat[down][n]\n                \n                count+=self.countSubMat(h)\n                \n        return count\n        \n        #[[1,0,1],[1,1,0],[1,1,0]]\n#     def numSubmat(self, mat: List[List[int]]) -> int:\n#         count=0\n        \n#         #filter size\n#         for i in range(len(mat)):\n#             for j in range(len(mat[0])):\n                \n#                 #for all position\n#                 for a in range(len(mat)):\n#                     if a+i<len(mat):\n#                         for b in range(len(mat[0])):\n#                             if b+j<len(mat[0]):\n#                                 tmp=0\n                                \n#                                 #for position inside filter\n#                                 for c in range(a,a+i+1,1):\n#                                     for d in range(b,b+j+1,1):\n#                                         tmp+=mat[c][d]\n                                        \n#                                 if tmp==((i+1)*(j+1)):\n#                                     count+=1\n#         return count\n#            #[[1,0,1],[1,1,0],[1,1,0]]             \n                        \n                        \n", "class Solution:\n    def countOnes(self, nums):\n        res = 0\n        length = 0\n        for i in range(len(nums)):\n            length = 0 if nums[i] == 0 else length + 1\n            res += length\n        return res\n        \n    def numSubmat(self, mat: List[List[int]]) -> int:\n        if not mat or not mat[0]:\n            return 0\n        \n        n, m = len(mat), len(mat[0])\n        res = 0\n        \n        for i in range(n):\n            h = [1] * m\n            \n            for j in range(i, n):\n                for k in range(m):\n                    if mat[j][k] == 0:\n                        h[k] = 0\n                res += self.countOnes(h)\n        \n        return res\n                \n", "class Solution:\n    def numSubmat(self, mat: List[List[int]]) -> int:\n        # O(m ^ 2 * n); Space: O(mn)\n        # focus on bottom left matrix, look left and look up\n        if not mat:\n            return 0\n        \n        m, n = len(mat), len(mat[0])\n        \n        dp = [[0] * (n + 1) for _ in range(m + 1)]\n        \n        res = 0\n        for i in range(1, m + 1):\n            for j in range(1, n + 1):\n                if mat[i - 1][j - 1]:\n                    dp[i][j] = dp[i][j - 1] + 1 # look left\n                    res += dp[i][j]\n                    # look above\n                    min_ones = dp[i][j]\n                    for k in range(i - 1, -1, -1):\n                        min_ones = min(min_ones, dp[k][j])\n                        res += min_ones\n        return res", "def scan(arr,height):\n    _sum, found = 0, 0\n    for x in arr:\n        _sum = 0 if x<height else (_sum+1)\n        if _sum:\n            found += _sum\n    return found\nclass Solution:\n    def numSubmat(self, mat: List[List[int]]) -> int:\n        r, result = len(mat), 0\n        for i in range(r):\n            row     = mat[i]\n            result += scan(row,1)\n            for k in range(i+1,r):\n                row = [ x+mat[k][j] for j,x in enumerate(row) ]\n                result += scan(row,k-i+1)\n        return result", "\nclass Solution:\n    def scan(self, arr,height):\n        _sum, found = 0, 0\n        for x in arr:\n            _sum = 0 if x<height else (_sum+1)\n            if _sum:\n                found += _sum\n        return found\n    \n    def numSubmat(self, mat: List[List[int]]) -> int:\n        r, result = len(mat), 0\n        for i in range(r):\n            row     = mat[i]\n            result += self.scan(row,1)\n            for k in range(i+1,r):\n                row = [ x+mat[k][j] for j,x in enumerate(row) ]\n                result += self.scan(row,k-i+1)\n        return result", "# class Solution:\n#     def numSubmat(self, mat: List[List[int]]) -> int:\n#         n, m = len(mat), len(mat[0])\n#         cache = {}\n        \n#         for rows in range(1, n + 1):\n#             for cols in range(1, m + 1):\n#                 for i in range(n):\n#                     for j in range(m):\n                        \n#                         if i + rows <= n and j + cols <= m:\n#                             if rows == 1 and cols == 1:\n#                                 if mat[i][j] == 1:\n#                                     cache[(i, j, rows, cols)] = 1\n#                             else:\n#                                 if rows > 1 and (i, j, rows - 1, cols) in cache and (i + rows - 1, j, 1, cols) in cache:\n#                                     cache[(i, j, rows, cols)] = 1\n\n#                                 elif cols > 1 and (i, j, rows, cols - 1) in cache and (i, j + cols - 1, rows, 1) in cache:\n#                                     cache[(i, j, rows, cols)] = 1\n        \n#         return len(cache)\n\nclass Solution:\n    def numSubmat(self, mat: List[List[int]]) -> int:\n        n, m = len(mat), len(mat[0])\n        \n        def num_submat_at(a, b):\n            c = 0\n            bound = m\n            \n            i = a\n            while i < n:\n                j = b\n                while j < bound:\n                    if mat[i][j]:\n                        c += 1\n                    else:\n                        bound = j\n                    \n                    j += 1\n                i += 1\n            return c\n    \n        total_c = 0\n        for i in range(n):\n            for j in range(m):\n                total_c += num_submat_at(i, j)\n\n        return total_c", "from typing import List\n\n\ndef matrices_in_rect(rows: int, cols: int) -> int:\n    return int((cols * (cols + 1) / 2) * (rows * (rows + 1) / 2))\n\n\nclass Solution:\n    def numSubmat(self, mat: List[List[int]]) -> int:\n        def count_rectangles(start_row: int, start_col: int) -> int:\n            rows, cols = len(mat), len(mat[0]) if mat else 0\n            count = 0\n\n            max_col = cols\n\n            for row in range(start_row, rows):\n                if mat[row][start_col] != 1:\n                    break\n\n                for col in range(start_col, max_col):\n                    if mat[row][col] != 1:\n                        break\n\n                    max_col = col + 1\n                    count += 1\n\n            return count\n\n        rows, cols = len(mat), len(mat[0]) if mat else 0\n        count = 0\n        for row in range(rows):\n            for col in range(cols):\n                count += count_rectangles(row, col)\n\n        return count\n\n    def numSubmat1(self, mat: List[List[int]]) -> int:\n        rows, cols = len(mat), len(mat[0]) if mat else 0\n        sizes = [[(0, 0)] * (cols + 1) for _ in range(rows + 1)]\n\n        for row in range(rows):\n            for col in range(cols):\n                if mat[row][col] == 1:\n                    sizes[row + 1][col + 1] = (\n                        min(sizes[row][col + 1][0], sizes[row][col][0]) + 1,\n                        min(sizes[row + 1][col][1], sizes[row][col][1]) + 1,\n                    )\n\n        print(sizes)\n        return 0\n", "class Solution:\n    def numSubmat(self, mat: List[List[int]]) -> int:\n        def oneDim(mat):\n            res = 0\n            length = 0\n            for el in mat:\n                if el == 0:\n                    length = 0\n                else:\n                    length += 1\n                res += length\n            return res\n        \n        res = 0\n        M = len(mat)\n        N = len(mat[0])\n        for top in range(M):\n            h = [1] * N\n            for bot in range(top, M):\n                for i in range(N):\n                    h[i] *= mat[bot][i]\n                res += oneDim(h)\n\n        return res", "class Solution:\n    #Version 1: DP\n    #left[i][j] is the longest 1 on the right hand side ending at mat[i][j]\n    #up[i][j] is the longest 1 above mat[i][j]\n    #TC: O(mnn), SC: O(mn)\n    '''\n    def numSubmat(self, mat: List[List[int]]) -> int:\n        m = len(mat)\n        n = len(mat[0])\n        left = [[0]*n for _ in range(m)]\n        up = [[0]*n for _ in range(m)]\n        \n        for k in range(m):\n            count = 0\n            for v in range(n):\n                if mat[k][v] == 1:\n                    count += 1\n                else:\n                    count = 0\n                left[k][v] = count\n                    \n        for v in range(n):\n            count = 0\n            for k in range(m):\n                if mat[k][v] == 1:\n                    count += 1\n                else:\n                    count = 0\n                up[k][v] = count\n            \n        ans = 0\n        for k in range(m):\n            for v in range(n):\n                if mat[k][v] == 1:\n                    current = up[k][v]\n                    for j in range(left[k][v]):\n                        current = min(current, up[k][v-j])\n                        ans += current\n                    #print(k, v, ans, left[k][v], right[k][v], up[k][v], down[k][v])\n        return ans\n    '''\n    \n    #Version 2: Stack and dp\n    #Consider the histogram in the first m rows\n    #dp[k] stores the the number of submatrices using mat[m][k] as the right bottom\n    #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]\n    #TC: O(mn), SC: O(n)\n    def numSubmat(self, mat: List[List[int]]) -> int:\n        m = len(mat)\n        n = len(mat[0])\n        ans = 0\n        h = [0]*n\n        for k in range(m):\n            for v in range(n):\n                if mat[k][v] == 1:\n                    h[v] += 1\n                else:\n                    h[v] = 0\n\n            dp = [0]*n\n            # stack = []\n            # for v in range(n):\n            #     while stack and h[stack[-1]] >= h[v]:\n            #         stack.pop()\n            #     if not stack:\n            #         dp[v] = h[v] * (v+1)\n            #     else:\n            #         dp[v] = dp[stack[-1]] + (v - stack[-1])*h[v]\n            #     stack.append(v)\n            #     ans += dp[v]\n            dp = [0]*(n+1)\n            stack = [[-1, 0]]\n            for v in range(n):\n                while stack and stack[-1][0] >= h[v]:\n                    stack.pop()\n                dp[v+1] = dp[stack[-1][1]] + (v + 1 - stack[-1][1])*h[v]\n                stack.append([h[v], v+1])\n                ans += dp[v+1]\n            #print(k, h, dp)\n        return ans\n    \n", "\\\"\\\"\\\"\ngoogle onsite \n\u4e8c\u7ef4\u77e9\u9635\u5305\u542b0\u548c1\u3002\u95ee\u75310\u7ec4\u6210\u7684sub rectangle\u6709\u591a\u5c11\u4e2a\uff0c\u8fd9\u4e2a\u662f\u9762\u7ecf\u9898\n\n\u6211\u662f\u8fd9\u6837\u60f3\u7684\u4e0d\u77e5\u9053\u5bf9\u4e0d\u5bf9\uff0c\u8003\u8651\u4ee5(i, j)\u4e3a\u53f3\u4e0b\u89d2\u7684\u6700\u5927\u6b63\u65b9\u5f62\u8fb9\u957f\uff0c\u8fd9\u4e2a\u5c31\u662flc 221\u3002\u7136\u540e\u5982\u679c\u4ee5(i, j)\u4e3a\u53f3\u4e0b\u89d2\u7684\u6700\u5927\u6b63\u65b9\u5f62\u8fb9\u957f\u662fa\uff0c\u5219\u4ee5\u5b83\u4e3a\u53f3\u4e0b\u89d2\u7684\u6b63\u65b9\u5f62\u6570\u76ee\u662fa\uff0c\u6240\u4ee5\u628a\u8fd9\u4e9b\u52a0\u8d77\u6765\u5c31\u597d\n\u56e0\u6b64\u7528\u4ee5\u4e0b dp\u65b9\u6cd5\n\ndp[i][j] \u4ee5(i, j)\u4e3a\u53f3\u4e0b\u9876\u70b9\u7684\u6700\u5927\u51681\u77e9\u9635\u7684\u8fb9\u957f. \u4e5f\u8868\u793a \u4ee5\uff08i,j\uff09\u4e3a\u53f3\u4e0b\u89d2\u6b63\u65b9\u5f62\u6570\u91cf\n\u7b54\u6848\u4e3a sum(dp[i][j])\n\\\"\\\"\\\"\n\n\\\"\\\"\\\"\nGoogle onsite\n\u7ed9\u4e00\u4e2a\u75310\uff0c1\u7ec4\u6210\u7684\u6570\u7ec4\uff0c\u7b97\u5b50\u6570\u7ec4\u5168\u662f0\u7684\u4e2a\u6570\u3002 e.g.[0,0,1,0] \u8fd4\u56de4\nfollow up: \u8f93\u5165\u662f\u4e8c\u7ef4\u77e9\u9635\uff0c\u7b97\u5b50\u77e9\u9635\u5168\u662f0\u7684\u4e2a\u6570\n\\\"\\\"\\\"\n\n\\\"\\\"\\\"\n\n\u56fa\u5b9a\u4e0a\u4e0b\u8fb9\u754c\uff0c\u627e\u5230\u4ee5\u5f53\u524d\u957f\u5ea6\u4e3a\u77e9\u5f62\u9ad8\u7684 \u77e9\u5f62\u6570\u91cf\uff0c\u6700\u540e\u5f97\u5230\u603b\u6570\u91cf\n\nfix up boundary and bottom boundary then find all submatrix with this height \nfor 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 \nthan we convert this 2d problem to 1d, we just need to calculate how many rec with all ones in it in this array \n\nNote: 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.\n\n\nTime O(M * N * M)\nSpace O(M * N )\n\\\"\\\"\\\"\nclass Solution:\n    def numSubmat(self, mat: List[List[int]]) -> int:\n        if not mat or not mat[0]:\n            return 0 \n        n = len(mat)\n        m = len(mat[0])\n        count = 0\n        # enumerate top and bottom boundary  \n        for top in range(n):\n            arr = [1] * m\n            for bottom in range(top, n):\n                # convert 2d to 1d array \n                for col in range(m):\n                    arr[col] &= mat[bottom][col]\n                # get all count of submatrices whose height = bottome - top\n                count += self.get_arr_ones_count(arr)\n        return count \n    # use curr num as the right boundary of the rectangle \n    def get_arr_ones_count(self, arr):\n        res = 0\n        count = 0\n        for num in arr:\n            if num == 0:\n                count = 0\n            else:\n                count += 1 \n                res += count \n        return res \n# [[1,0,1],\n#  [1,1,0],\n#  [1,1,0]]\n# arr = [1,0,1], top=0,bottom=0, count = 2\n# arr = [2,1,1], top=0,bottom=1, count = 2\n\n", "class Solution:\n    def numSubmat(self, mat: List[List[int]]) -> int:\n        # https://www.youtube.com/watch?v=EqzTpLSYK6g\n        # O(m ^ 2 * n); Space: O(mn)\n        # focus on bottom left matrix, look left and look up\n        # 0 0 0 0      0 0 0 0\n        # 0 1 1 0  ->  0 1 2 0\n        # 0 0 1 0      0 0 1 0\n        if not mat:\n            return 0\n        \n        m, n = len(mat), len(mat[0])\n        \n        dp = [[0] * (n + 1) for _ in range(m + 1)]\n        \n        res = 0\n        for i in range(1, m + 1):\n            for j in range(1, n + 1):\n                if mat[i - 1][j - 1]:\n                    dp[i][j] = dp[i][j - 1] + 1 # look left\n                    res += dp[i][j]\n                    # look above\n                    min_ones = dp[i][j]\n                    for k in range(i - 1, -1, -1):\n                        min_ones = min(min_ones, dp[k][j])\n                        res += min_ones\n        return res", "class Solution:\n    def numSubmat(self, mat: List[List[int]]) -> int:\n        counter = 0\n\n        rows = len(mat)\n\n        if rows > 0:\n            columns = len(mat[0])\n\n            for i in range(rows):\n                for j in range(columns):\n\n                    max_width = 0\n                    max_height = 0\n\n                    if mat[i][j] == 1:\n                        counter += 1\n                        max_width += 1\n                        max_height += 1\n\n                        for k in range(j + 1, columns):\n                            if mat[i][k] == 1:\n                                counter += 1\n                                max_width += 1\n                            else:\n                                break\n\n                        for l in range(i + 1, rows):\n                            if mat[l][j] == 1:\n                                counter += 1\n                                max_height += 1\n                                m_w = 1\n\n                                for m in range(j + 1, columns):\n                                    if mat[l][m] == 1 and m_w < max_width:\n                                        counter += 1\n                                        m_w += 1\n                                    else:\n                                        max_width = min(max_width, m_w)\n                                        break\n                            else:\n                                break\n                    else:\n                        continue\n\n        return counter\n", "class Solution:\n    def numSubmat(self, mat: List[List[int]]) -> int:\n        \n        info=[[[] for i in range(len(mat[0]))]for j in range(len(mat))]\n        \n        result=0\n        for i in range(len(mat)):\n            for j in range(len(mat[0])):\n                if i==0 and j==0:\n                    info[i][j].append(mat[i][j])\n                    result+=mat[i][j]\n                elif i==0 and j!=0:\n                    if mat[i][j]==1:\n                        info[i][j].append(info[i][j-1][0]+1)\n                        result+=info[i][j][0]\n                    else:\n                        info[i][j].append(0)\n                elif j==0 and i!=0:\n                    if mat[i][j]==1:\n                        info[i][j].append(1)\n                        if mat[i-1][j]==1:\n                            info[i][j]+=info[i-1][j]\n                        result+=sum(info[i][j])  \n                    else:\n                        info[i][j].append(0)\n                else:\n                    if mat[i][j]==1:\n                        info[i][j].append(info[i][j-1][0]+1)\n                        if mat[i-1][j]==1:\n                            for index in range(len(info[i-1][j])):\n                                if index+1 <len(info[i][j-1]):\n                                    info[i][j].append(min(info[i][j-1][index+1]+1,info[i-1][j][index]))\n                                else:\n                                    info[i][j].append(1)\n                        result+=sum(info[i][j])      \n                    else:\n                        info[i][j].append(0)\n        \n        return result\n                    \n                \n", "class Solution:\n    def numSubmat(self, mat: List[List[int]]) -> int:\n        if not mat:\n            return 0\n        \n        m, n = len(mat), len(mat[0])\n        \n        dp = [[0] * (n + 1) for _ in range(m + 1)]\n        \n        res = 0\n        for i in range(1, m + 1):\n            for j in range(1, n + 1):\n                if mat[i - 1][j - 1]:\n                    dp[i][j] = dp[i][j - 1] + 1\n                    res += dp[i][j]\n                    min_ones = dp[i][j]\n                    for k in range(i - 1, -1, -1):\n                        min_ones = min(min_ones, dp[k][j])\n                        res += min_ones\n        return res", "class Solution:\n    def numSubmat(self, mat: List[List[int]]) -> int:\n        rows = len(mat)\n        cols = len(mat[0])\n        print(\\\"rows = {}; cols = {}\\\".format(rows, cols))\n        \n        cnt = 0\n        \n        for tl_row in range(0, rows):\n            for tl_col in range(0, cols):\n                # May be \\\"retracted\\\" as we go along:\n                max_width = cols - tl_col\n                \n                for height in range(1, rows - tl_row + 1):\n                    for width in range(1, max_width + 1):\n                        cell = mat[tl_row + height - 1][tl_col + width - 1]\n                        if cell == 1:\n                            cnt += 1\n                            continue\n                        else:\n                            max_width = width - 1\n                            break\n                            \n                    if max_width == 0:\n                        break\n\n        return cnt                        \n        ", "class Solution:\n    def numSubmat(self, mat: List[List[int]]) -> int:\n        r = len(mat)\n        c = len(mat[0])\n        res = 0\n        for up in range(r):\n            ans = [1] * c\n            for down in range(up, r):\n                for j in range(c):\n                    ans[j] = ans[j] & mat[down][j]\n                res += self.cal(ans)\n        return res\n    \n    def cal(self, ans):\n        res = 0\n        cur = 0\n        n = len(ans)\n        for i in range(n):\n            if ans[i] == 0:\n                cur = 0\n            else:\n                cur += 1\n                res += cur\n        return res", "class Solution:\n    def numSubmat(self, mat: List[List[int]]) -> int:\n        \n        n=len(mat)\n        m=len(mat[0])\n\n        counts=[[0]*m for j in range(n)]\n        \n        for i in range(n):\n            for j in range(m-1, -1, -1):\n                if mat[i][j]==1:\n                    counts[i][j]+=1+(counts[i][j+1] if j+1<m else 0)\n        res=0            \n        for i in range(n):\n            for j in range(m):\n                if mat[i][j]==1:\n                    mins=float('inf')\n                    for k in range(i, n):\n                        mins=min(mins, counts[k][j])\n                        res+=mins\n                        \n        return res", "class Solution:\n    def numSubmat2(self, mat: List[List[int]]) -> int:\n        \\\"\\\"\\\"O(m^2*n)\\\"\\\"\\\"\n        def calc(arr):\n            res = 0\n            leng = 0\n            for i in range(len(arr)):\n                leng = 0 if arr[i] == 0 else leng + 1\n                res += leng\n            return res\n        m, n = len(mat), len(mat[0])\n        res = 0\n        for i in range(m):\n            arr = [1] * n\n            for j in range(i, m):\n                for k in range(n):\n                    arr[k] &= mat[j][k]\n                res += calc(arr)\n        return res\n    \n    def numSubmat(self, mat: List[List[int]]) -> int:\n        \\\"\\\"\\\"O(m*n^2)\\\"\\\"\\\"\n        def calc(arr):\n            res = 0\n            leng = 0\n            for i in range(len(arr)):\n                leng = 0 if arr[i] == 0 else leng + 1\n                res += leng\n            return res\n        def calc2(arr):\n            res = 0\n            for c, g in itertools.groupby(arr):\n                if c == 1:\n                    n = len(list(g))\n                    res += n * (n + 1)//2\n            return res\n        m, n = len(mat), len(mat[0])\n        res = 0\n        for i in range(n):\n            arr = [1] * m\n            for j in range(i, n):\n                for k in range(m):\n                    arr[k] &= mat[k][j]\n                res += calc2(arr)\n        return res", "class Solution:\n    def numSubmat(self, mat: List[List[int]]) -> int:\n        a = mat\n        m, n = len(a), len(a[0])\n        def hist(h):\n            ret = [0] * n\n            s = []\n            for i, x in enumerate(h):\n                while s and h[s[-1]] >= x:\n                    s.pop()\n                if s:\n                    j = s[-1]\n                    ret[i] = ret[j] + (i - j) * x\n                else:\n                    ret[i] = (i + 1) * x\n                s.append(i)\n            return sum(ret)\n        h = [0] * n\n        ans = 0\n        for row in a:\n            for j in range(n):\n                h[j] = row[j] + h[j] if row[j] else 0\n            ans += hist(h)\n        return ans\n", "class Solution:\n    def numSubmat(self, mat: List[List[int]]) -> int:\n        #refer https://www.youtube.com/watch?v=8miqwSN3EFo&ab_channel=HappyCoding\n        m, n = len(mat), len(mat[0])\n        \n        one_counts = [[0] * n for _ in range(m)]\n        \n        for i in range(m):\n            for j in range(n - 1, -1, -1):\n                if mat[i][j] == 1:\n                    if j < n - 1:\n                        one_counts[i][j] += 1 + one_counts[i][j + 1]\n                    else:\n                        one_counts[i][j] = 1\n        \n        ans = 0\n        for i in range(m):\n            for j in range(n):\n                if mat[i][j] != 1:\n                    continue\n                min_width = sys.maxsize\n                for k in range(i, m):\n                    min_width = min(min_width, one_counts[k][j])\n                    ans += min_width\n        \n        return ans\n        \n", "class Solution:\n    def numSubmat(self, mat: List[List[int]]) -> int:\n                    \n        def helper(arr):\n            count = 0\n            curr = 0\n            \n            for item in arr:\n                \n                if item != 1:\n                    curr = 0\n                else:\n                    curr += 1\n                \n                count += curr\n\n            return count\n        \n        result = 0\n        for x1 in range(len(mat)):\n            \n            zeros = [1 for x in range(len(mat[0]))]\n            \n            for x2 in range(x1, len(mat)):\n                \n                for col in range(len(mat[0])):\n                    \n                    zeros[col] &= mat[x2][col]\n                \n                result += helper(zeros)\n        \n        return result", "class Solution:\n    def numSubmat(self, mat: List[List[int]]) -> int:\n        # O(m ^ 2 * n); Space: O(mn)\n        # focus on bottom left matrix, look left and look up\n        # 0 0 0 0      0 0 0 0\n        # 0 1 1 0  ->  0 1 2 0\n        # 0 0 1 0      0 0 1 0\n        if not mat:\n            return 0\n        \n        m, n = len(mat), len(mat[0])\n        \n        dp = [[0] * (n + 1) for _ in range(m + 1)]\n        \n        res = 0\n        for i in range(1, m + 1):\n            for j in range(1, n + 1):\n                if mat[i - 1][j - 1]:\n                    dp[i][j] = dp[i][j - 1] + 1 # look left\n                    res += dp[i][j]\n                    # look above\n                    min_ones = dp[i][j]\n                    for k in range(i - 1, -1, -1):\n                        min_ones = min(min_ones, dp[k][j])\n                        res += min_ones\n        return res", "class Solution:\n    def numSubmat(self, mat: List[List[int]]) -> int:\n        if not mat:\n            return 0\n        \n        m, n = len(mat), len(mat[0])\n        \n        dp = [[0] * (n + 1) for _ in range(m + 1)]\n        \n        res = 0\n        for i in range(1, m + 1):\n            for j in range(1, n + 1):\n                if mat[i - 1][j - 1]:\n                    dp[i][j] = dp[i][j - 1] + 1 # walk left\n                    res += dp[i][j]\n                    # walk above\n                    min_ones = dp[i][j]\n                    for k in range(i - 1, -1, -1):\n                        min_ones = min(min_ones, dp[k][j])\n                        res += min_ones\n        return res", "class Solution:\n    def numSubmat(self, mat: List[List[int]]) -> int:\n        rows = len(mat)+1\n        cols = len(mat[0])+1\n        dp = [[0 for x in range(cols)] for y in range(rows)]\n        for i in range(1, rows):\n            dp[i][0] = 0\n        for j in range(1, cols):\n            dp[0][j] = 0\n        \n       \n        res = 0\n        #left most\n        for i in range(1, rows):\n            for j in range(1, cols):\n                if mat[i-1][j-1] == 1:\n                    dp[i][j] = dp[i][j-1] + 1\n                    res += dp[i][j]\n                    min_ones = dp[i][j]\n                    #upper most\n                    for k in range(i-1, -1, -1):\n                        min_ones = min(dp[k][j], min_ones)\n                        res += min_ones\n        return res", "class Solution:\n    def numSubmat(self, mat: List[List[int]]) -> int:\n        dp = [[0] * (len(mat[0]) + 1) for _ in range(len(mat) + 1)]\n        res = 0\n        for i in range(1, len(mat) + 1):\n            for j in range(1, len(mat[0]) + 1):\n                if mat[i - 1][j - 1] == 1:\n                    dp[i][j] = 1 + dp[i][j - 1]\n                    res += dp[i][j]\n                    \n                    minRec = dp[i][j]\n                    for k in range(i - 1, -1, -1):\n                        minRec = min(minRec, dp[k][j])\n                        res += minRec\n        return res\n", "class Solution:\n\n    def numSubmat(self, mat: List[List[int]]) -> int:\n        res = 0\n        m = len(mat)\n        n = len(mat[0])\n        data = [[0 for _ in range(n)] for _ in range(m)] # [i, j] stores consecutive number of 1s from the cell upwards\n        for row in range(m): # row\n            for col in range(n): # col\n                if not mat[row][col]:\n                    continue\n                data[row][col] = 1 if row == 0 else data[row - 1][col] + 1\n                smallest = data[row][col]\n                res += smallest\n                for j in range(col - 1, -1, -1):\n                    smallest = min(smallest, data[row][j])\n                    res += smallest\n        return res\n\n    \n    def numSubmat_v1(self, mat: List[List[int]]) -> int:\n        \\\"\\\"\\\"My O(n^4) algorithm\n        \\\"\\\"\\\"\n        res = 0\n        m = len(mat)\n        n = len(mat[0])\n        data = [[set() for _ in range(n)] for _ in range(m)] # [i, j] stores valid rectangle sizes represented by longth & width\n        for row in range(m): # row\n            for col in range(n): # col\n                if not mat[row][col]:\n                    continue\n                data[row][col].add((1,1))\n                res += 1\n                if col > 0:\n                    for e in data[row][col - 1]:  # look at all rectangles of the left cell\n                        if e[1] == 1:\n                            data[row][col].add((e[0] + 1, 1))\n                            res += 1\n                        elif row > 0 and (1, e[1] - 1) in data[row - 1][col]:\n                            data[row][col].add((e[0] + 1, e[1]))\n                            res += 1\n                if row > 0:\n                    for e in data[row - 1][col]:\n                        if e[0] == 1:\n                            data[row][col].add((1, e[1] + 1))\n                            res += 1\n        return res\n                \n                ", "class Solution:\n    def numSubmat(self, mat: List[List[int]]) -> int:\n        # similar to 1277\n        # but we only look left and look up\n        # then take min\n        count = 0\n        for i in range(len(mat)):\n            for j in range(len(mat[0])):\n                if mat[i][j]==1:\n                    # look left\n                    mat[i][j] = mat[i][j-1]+1 if j>0 else 1\n                    count += mat[i][j]\n                    # look up\n                    # need to go up to top\n                    # to count all possible recs\n                    min_ones = mat[i][j]\n                    for k in range(i-1, -1, -1):\n                        min_ones = min(min_ones, mat[k][j])\n                        count += min_ones\n        return count", "class Solution:   \n    def numSubmat(self, mat: List[List[int]]) -> int:    \n        M=len(mat)\n        N=len(mat[0])\n        histogram=[[0 for _ in range(N)] for _ in range(M)] \n        dp=[[0 for _ in range(N)] for _ in range(M)] \n        ## monoI stack (index) for storing histogram \n        stack=[[] for _ in range(N)] \n        \n        for m in range(M):\n            for n in range(N):\n                if n==0:\n                    histogram[m][n]=mat[m][n]\n                else:\n                    histogram[m][n]=histogram[m][n-1]+1 if mat[m][n]==1 else 0\n        \n        res=0  \n        for bottom in range(M):\n            for right in range(N):\n                while stack[right] and histogram[stack[right][-1]][right]>histogram[bottom][right]:\n                    stack[right].pop()\n                if stack[right]:\n                    dp[bottom][right]=dp[stack[right][-1]][right]\\\\\n                                        +histogram[bottom][right]*(bottom-stack[right][-1])       \n                else:\n                    dp[bottom][right]=histogram[bottom][right]*(bottom+1)\n                    \n                stack[right].append(bottom)\n                res+=dp[bottom][right]  \n                \n        return res\n\n    \n#-----------|||||||||||||||||||||||||||||||||||||||||||||||||-------------------#   \n\n#     ## O(M*N*M)\n#     def numSubmat(self, mat: List[List[int]]) -> int:\n#         M=len(mat)\n#         N=len(mat[0])\n        \n#         # num of consecutive ones to the left of (x,y) in the same row\n#         histogram=[[0 for _ in range(N)] for _ in range(M)] \n\n#         for m in range(M):\n#             for n in range(N):\n#                 if n==0:\n#                     histogram[m][n]=mat[m][n]\n#                 else:\n#                     histogram[m][n]=histogram[m][n-1]+1 if mat[m][n]==1 else 0\n#         res=0          \n#         for bottom in range(M):\n#             for right in range(N):\n#                 Min=histogram[bottom][right]\n#                 for upper in range(bottom+1)[::-1]:      \n#                     Min=min(Min,histogram[upper][right])\n#                     if Min==0:\n#                         break\n#                     res+=Min\n                    \n#         return res\n\n#-----------|||||||||||||||||||||||||||||||||||||||||||||||||-------------------#                    \n        \n#     ## Brute Force w/ Pruning O(N^2*M^2)\n#     def numSubmat(self, mat: List[List[int]]) -> int:\n#         M=len(mat)\n#         N=len(mat[0])\n#         res=0       \n        \n#         for top in range(M):\n#             for left in range(N):\n#                 bound=N ## to bound the right pointer\n#                 for bottom in range(top,M):                    \n#                     right=left\n#                     while right<bound:\n#                         if mat[bottom][right]==1:\n#                             res+=1\n#                             right+=1\n#                         else:\n#                             bound=right\n#                             break\n#         return res                  \n                        \n                        \n                    \n                \n        ", "class Solution:\n    def numSubmat(self, mat: List[List[int]]) -> int:\n        m, n = len(mat), len(mat[0])\n        \n        def count_sub(i, j):\n            max_c = n\n            count = 0 \n            for r in range(i, m):\n                for c in range(j, max_c):\n                    if mat[r][c] == 1:\n                        count += 1\n                    else:\n                        max_c = c\n                        break\n            return count\n        \n        \n        ans = 0\n        for i in range(m):\n            for j in range(n):\n                if mat[i][j]:\n                    ans += count_sub(i, j)\n        return ans", "class Solution:\n    def numSubmat(self, mat: List[List[int]]) -> int:\n\n        def countOneRow(A):\n            res, length = 0, 0\n            for a in A:\n                length =  0 if a == 0 else length + 1\n                res += length\n            return res\n\n        res, M, N = 0, len(mat), len(mat[0])\n        \n        for up in range(M):\n            onesCol = [1] * N\n            for down in range(up, M):\n                for i in range(N):\n                    onesCol[i] &= mat[down][i]\n                res += countOneRow(onesCol)\n        return res\n                \n            \n", "class Solution:\n    def numSubmat(self, mat: List[List[int]]) -> int:\n        rows,cols = len(mat),len(mat[0])  \n        \n        def one_d_sum(h):\n            ans = 0\n            length = 0\n            for i in range(len(h)):\n                if h[i] == 1:\n                    length += 1\n                else:\n                    length = 0\n                ans += length\n            return ans\n        \n        \n        ans = 0\n        for top_row in range(rows):\n            h = [1] * cols\n            for bottom_row in range(top_row,rows):\n                for k in range(cols):\n                    h[k] = h[k] & mat[bottom_row][k]\n                ans += one_d_sum(h)\n        return ans\n        \n        \n        \n        \n        \n        \n        \n        \n        \n        \n        \n\n\n\n\n\n\n\n\n\n\n#         h, w = len(mat), len(mat[0])\n        \n#         # dp table:\n#         # record the maximum length of continuous 1 from left-most column to specified column\n#         dp_acc_of_1 = [ [ 0 for _ in range(w)] for _ in range(h) ]\n        \n#         for y in range(h):\n#             for x in range(w):\n                \n#                 if x == 0:\n#                     # left-most column\n#                     dp_acc_of_1[y][x] = mat[y][x]\n                    \n#                 else:\n#                     # not left-most column\n#                     if mat[y][x] == 1:\n#                         dp_acc_of_1[y][x] = dp_acc_of_1[y][x-1] + 1\n                        \n\n#         counter_of_rectangle = 0\n        \n#         for y in range(h):\n#             for x in range(w):\n                \n#                 # update the total number of rectangle, whose bottom right anchor point is [y][x]\n                \n#                 minimum_width = dp_acc_of_1[y][x]\n                \n#                 for h_idx in range(y, -1, -1):\n#                     minimum_width = min(minimum_width, dp_acc_of_1[h_idx][x])\n#                     counter_of_rectangle += minimum_width\n                    \n#                     if minimum_width == 0:\n#                         # no chance to make rectangle\n#                         break\n                        \n#         return counter_of_rectangle\n", "class Solution:\n    def numSubmat(self, mat: List[List[int]]) -> int:\n        \n        row = len(mat)\n        col = len(mat[0])\n        res = 0\n\n        def calculate1dArray(arr):\n            ans = 0\n            pre = 0\n            for i, a in enumerate(arr):\n                if a == 1:\n                    pre += 1\n                    ans += pre\n                else:\n                    pre = 0\n            return ans \n        \n        for a in range(row):\n            arr = [1] * col\n            for b in range(a, row):\n                for c in range(col):\n                    arr[c] &= mat[b][c] \n                res += calculate1dArray(arr)\n        return res \n", "class Solution:\n    def numSubmat(self, mat: List[List[int]]) -> int:\n        \n        # \u751f\u6210\u76f4\u65b9\u56fehistogram\n        def countOneRow(arr):\n            res = 0\n            l = 0\n            for i in range(len(arr)):\n                if arr[i] == 0:\n                    l = 0\n                else: l = l + 1\n                res += l # \u4ee5\u5f53\u524d\u4e3a\u6700\u53f3\uff0c\u53ef\u4ee5\u5f62\u6210l\u4e2a\u77e9\u5f62\n            return res\n        \n        rows = len(mat)\n        cols = len(mat[0])\n        res = 0\n        for top in range(rows):\n            h = [1] * cols\n            l = 0\n            for bottom in range(top, rows):\n                for c in range(cols):\n                    # \u6bcf\u4e00\u884c\u90fd\u8ddftop\u6765merge\uff0c\u56e0\u4e3a\u4e2d\u95f4\u5fc5\u987b\u6240\u6709\u683c\u90fd\u662f1\uff0c\u624d\u80fd\u5f62\u6210\u4e00\u4e2a\u77e9\u5f62\n                    h[c] &= mat[bottom][c]\n                    l |= h[c]\n                res += countOneRow(h)\n                if not any(h): break\n        return res", "class Solution:\n    def numSubmat(self, mat: List[List[int]]) -> int:\n        \n        res = 0\n        \n        m, n = len(mat), len(mat[0])\n        \n        dp = [[0] * n for i in range(m)]\n        \n        for i in range(m):\n            \n            prev = 0\n            \n            for j in range(n - 1, -1, -1):\n                \n                if mat[i][j] == 1:\n                    \n                    dp[i][j] = prev + 1\n                    \n                    prev = dp[i][j]\n                    \n                else:\n                    \n                    prev = 0\n                    \n        for i in range(m):\n            \n            for j in range(n):\n                \n                if mat[i][j] == 1:\n                    \n                    min_right = dp[i][j]\n                    \n                    for k in range(i, m):\n                        \n                        min_right = min(min_right, dp[k][j])\n                        \n                        res += min_right\n                        \n        return res\n", "class Solution:\n    def numSubmat(self, mat: List[List[int]]) -> int:\n        m, n = len(mat), len(mat[0])\n        \n        def count_sub(i, j):\n            max_c = n\n            count = 0 \n            for r in range(i, m):\n                for c in range(j, max_c):\n                    if mat[r][c] == 1:\n                        count += 1\n                    else:\n                        max_c = c\n                        break\n                if not max_c:\n                    break\n            return count\n        \n        \n        ans = 0\n        for i in range(m):\n            for j in range(n):\n                if mat[i][j]:\n                    ans += count_sub(i, j)\n        return ans", "class Solution:\n    def numSubmat(self, mat: List[List[int]]) -> int:\n        M=len(mat)\n        N=len(mat[0])\n        \n        mark=[[0 for _ in range(N)] for _ in range(M)]\n        \n        for m in range(M):\n            for n in range(N):\n                if n==0:\n                    mark[m][n]=mat[m][n]\n                else:\n                    mark[m][n]=mark[m][n-1]+1 if mat[m][n]==1 else 0\n        res=0          \n        for bottom in range(M):\n            for right in range(N):\n                Min=mark[bottom][right]\n                for upper in range(bottom+1)[::-1]:      \n                    Min=min(Min,mark[upper][right])\n                    res+=Min\n                    \n        return res\n                    \n        \n#     ## Brute Force w/ Pruning O(N^2*M^2)\n#     def numSubmat(self, mat: List[List[int]]) -> int:\n#         M=len(mat)\n#         N=len(mat[0])\n#         res=0       \n        \n#         for top in range(M):\n#             for left in range(N):\n#                 bound=N ## to bound the right pointer\n#                 for bottom in range(top,M):                    \n#                     right=left\n#                     while right<bound:\n#                         if mat[bottom][right]==1:\n#                             res+=1\n#                             right+=1\n#                         else:\n#                             bound=right\n#                             break\n#         return res                  \n                        \n                        \n                    \n                \n", "class Solution:\n    def countSubMat(self,rowmat:List[int])->int:\n        count=rowmat[0]\n        for i in range(1,len(rowmat)):\n            rowmat[i]=0 if rowmat[i]==0 else (rowmat[i-1]+rowmat[i])\n            count+=rowmat[i]\n        \n        # length=0\n        # count=0\n        # for i in range(len(rowmat)):\n        #     length=0 if rowmat[i]==0 else (length+1)\n        #     count+=length\n        return count\n    \n    def numSubmat(self, mat: List[List[int]]) -> int:\n        count=0\n        \n        for m in range(len(mat)):\n            \n            h=[1 for _ in range(len(mat[0]))]\n            for down in range(m,len(mat),1):\n                for n in range(len(mat[0])):\n                    h[n]=h[n]and mat[down][n]\n                \n                count+=self.countSubMat(h)\n                \n        return count\n        \n        #[[1,0,1],[1,1,0],[1,1,0]]\n#     def numSubmat(self, mat: List[List[int]]) -> int:\n#         count=0\n        \n#         #filter size\n#         for i in range(len(mat)):\n#             for j in range(len(mat[0])):\n                \n#                 #for all position\n#                 for a in range(len(mat)):\n#                     if a+i<len(mat):\n#                         for b in range(len(mat[0])):\n#                             if b+j<len(mat[0]):\n#                                 tmp=0\n                                \n#                                 #for position inside filter\n#                                 for c in range(a,a+i+1,1):\n#                                     for d in range(b,b+j+1,1):\n#                                         tmp+=mat[c][d]\n                                        \n#                                 if tmp==((i+1)*(j+1)):\n#                                     count+=1\n#         return count\n#            #[[1,0,1],[1,1,0],[1,1,0]]             \n                        \n                        \n", "class Solution:\n    def numSubmat(self, mat: List[List[int]]) -> int:\n        m, n = len(mat), len(mat[0])\n        left = [[0 for j in range(n+1)] for i in range(m+1)]\n        for i in range(1, len(left)):\n            for j in range(1, len(left[0])):\n                if mat[i-1][j-1] == 1:\n                    left[i][j] = left[i][j-1] + 1\n        res = 0\n        for i in range(len(mat)):\n            for j in range(len(mat[0])):\n                minlen = float('inf')\n                for k in range(i, -1, -1):\n                    minlen = min(minlen, left[k+1][j+1])\n                    res += minlen\n        return res\n", "class Solution:\n    def numSubmat(self, mat: List[List[int]]) -> int:\n        # \u8fd9\u9053\u9898\u662f\u95ee\u6709\u591a\u5c11\u4e2asubmatrices\u6709all ones\n        # \u548c84Largest Rectangle in Histogram\u5f88\u50cf\n         \n        # \u89e3\u6cd51 - \u679a\u4e3e\u53f3\u4e0b\u89d2\n        m, n = len(mat), len(mat[0])\n        left_ones = [[0] * n for _ in range(m)]\n        for i in range(m):\n            for j in range(n):\n                if mat[i][j] == 0:\n                    left_ones[i][j] = 0\n                else:\n                    left_ones[i][j] = 1\n                    if j > 0:\n                        left_ones[i][j] += left_ones[i][j - 1]\n        \n#         res = 0\n#         for i in range(m):\n#             for j in range(n):\n#                 curr_left_ones = left_ones[i][j]\n#                 for k in range(i, -1, -1):\n#                     curr_left_ones = min(curr_left_ones, left_ones[k][j])\n#                     res += curr_left_ones\n        \n#         return res\n\n\n        res = 0\n        for j in range(n):\n            total = 0\n            stack = []\n            for i in range(m):\n                height = 1\n                total += left_ones[i][j]\n                while stack and stack[-1][0] > left_ones[i][j]:\n                    # \u5f39\u51fa\u7684\u65f6\u5019\u8981\u51cf\u53bb\u591a\u4e8e\u7684\u7b54\u6848\n                    total -= stack[-1][1] * (stack[-1][0] - left_ones[i][j])\n                    height += stack[-1][1]\n                    stack.pop()\n                res += total\n                stack.append((left_ones[i][j], height))\n\n        return res\n\n", "class Solution:\n    def numSubmat(self, mat: List[List[int]]) -> int:\n        if not mat or not mat[0]:\n            return 0\n        m, n = len(mat), len(mat[0])\n        hts = [0]*n\n        ans = 0\n        for i in range(m):\n            for j in range(n):\n                hts[j] = hts[j]+1 if mat[i][j] else 0\n            for j in range(n):\n                minh = m\n                for k in range(j, n):\n                    minh = min(minh, hts[k])\n                    ans += minh\n        return ans\n", "class Solution:\n    def numSubmat(self, mat: List[List[int]]) -> int:\n        res = 0\n        \n        for i in range(len(mat)):\n            row = [ 1 for _ in range(len(mat[0])) ]\n            for j in range(i, len(mat)):\n                for k in range(len(mat[0])):\n                    row[k] &= mat[j][k]\n                res += self.countRow(row)\n                \n        return res\n    \n    def countRow(self, row: List[int]) -> int:\n        res = length = 0\n        \n        for i, val in enumerate(row):\n            length = 0 if val == 0 else length + 1\n            res += length\n        \n        return res", "class Solution:\n    def numSubmat(self, mat: List[List[int]]) -> int:\n        \n        R = len(mat)\n        C = len(mat[0])\n        dp = [[None for i in range(C)] for j in range(R)]\n        \n        for i in range(R):\n            count = 0\n            for j in range(C-1,-1, -1):\n                if mat[i][j] == 1:\n                    count += 1\n                else:\n                    count = 0\n                dp[i][j] = count\n        \n        result = 0\n        for i in range(R):\n            for j in range(C):\n                mn = float(\\\"inf\\\")\n                for k in range(i, R):\n                    mn = min(mn, dp[k][j])\n                    result += mn\n        \n        return result\n", "class Solution:\n    def numSubmat(self, mat) -> int:\n        m, n = len(mat), len(mat[0])\n        res = 0\n        for up in range(m):\n            h = [1]*n\n            for down in range(up, m):\n                for k in range(n):\n                    h[k] &= mat[down][k]\n                res += self.countOneRow(h)\n        return res\n\n    def countOneRow(self, arr):\n        res, length = 0, 0\n        for i in range(len(arr)):\n            length = 0 if arr[i]==0 else length+1\n            res += length\n        return res\n", "class Solution:\n    def numSubmat(self, mat: List[List[int]]) -> int:\n        m,n = len(mat),len(mat[0])     \n        \n        dp = [[None for i in range(n)]for j in range(m)]\n        \n        for i in range(m):\n            count=0\n            \n            #It will find consecutive ones horizontally\n            for j in range(n-1,-1,-1):\n                if mat[i][j]:\n                    count+=1\n                else:\n                    count=0\n                dp[i][j]=count\n                \n                \n        ans = 0\n        \n        for i in range(m):\n            for j in range(n):\n                \n                #We will take min in that column\n                mn = float('inf')\n                for k in range(i,m):\n                    mn = min(mn,dp[k][j])\n                    ans+=mn\n                print()\n                    \n        return ans", "class Solution:\n    def numSubmat(self, mat: List[List[int]]) -> int:\n        if not mat:return 0\n        m,n = len(mat),len(mat[0])\n        res = 0\n        #RLE - Run length encoding\n        for i in range(m):\n            for j in range(n):\n                if  j:\n                    if mat[i][j]:\n                        mat[i][j] = mat[i][j-1] + 1\n                        \n        #Now,calculate all the rectangular submatrices from the RLE\n        print(mat)\n        for i in range(m):    \n            for j in range(n):\n                # (i,j) :top right of matrix\n                ans = mat[i][j]\n                for k in range(i,m):#bottom-right\n                    ans = min(ans,mat[k][j])\n                    res+= ans\n    \n        return res", "class Solution:\n    def numSubmat(self, mat: List[List[int]]) -> int:\n        if not mat:return 0\n        m,n = len(mat),len(mat[0])\n        res = 0\n        #RLE - Run length encoding\n        for i in range(m):\n            for j in range(n):\n                if  j:\n                    if mat[i][j]:\n                        mat[i][j] = mat[i][j-1] + 1\n                        \n        #Now,calculate all the rectangular submatrices from the RLE\n        print(mat)\n        for i in range(m):    \n            for j in range(n):\n                # (i,j) :top right of matrix\n                ans = mat[i][j]\n                for k in range(i,m):#bottom-right\n                    ans = min(ans,mat[k][j])\n                    res+= ans\n    \n        return res\n", "class Solution:\n    def numSubmat(self, mat: List[List[int]]) -> int:\n        n=len(mat)\n        m=len(mat[0])\n        \n        for i in range(n):\n            for j in range(m-2,-1,-1):\n                \n                if mat[i][j]:\n                    mat[i][j]+=mat[i][j+1]\n                    \n                    \n        ans=0\n        \n        for i in range(n):\n            for j in range(m):\n                mini=float(\\\"inf\\\")\n                for k in range(i,n):\n                    mini=min(mini,mat[k][j])\n                    \n                    ans+=mini\n                    \n        return ans\n                    \n        \n        \n        \n        \n        ", "class Solution:\n    def numSubmat(self, mat) -> int:\n\n        m, n = len(mat), len(mat[0])\n        consective = [0] * m\n        res = 0\n        for line in range(n):\n            for row in range(m):\n                if mat[row][line] == 1:\n                    consective[row] += 1\n                else:\n                    consective[row] = 0\n            stack = []\n            for i in range(m):\n                val = consective[i]\n                while stack and val <= stack[-1][0]:\n                    stack.pop()\n                stack.append((val, i))\n                for k in range(len(stack)):\n                    if k == 0:\n                        a, b = stack[k]\n                        res += a * (b + 1)\n                    else:\n                        a, b = stack[k - 1]\n                        c, d = stack[k]\n                        res += c * (d - b)\n        return res", "class Solution:\n    def numSubmat(self, mat: List[List[int]]) -> int:\n        # get potential widths of rectangles, then process downward for all rectangles defined by width\n        \n        # process widths\n        rows, cols = len(mat), len(mat[0])\n        for r in range(rows):\n            for c in range(1, cols):\n                mat[r][c] = 1 + mat[r][c-1] if mat[r][c] else 0\n        \n        # process downwards for each potential width\n        rectangles = 0\n        for r in range(rows):\n            for c in range(cols):\n                width = mat[r][c]\n                if width:\n                    row = r\n                    while row < rows:\n                        width = min(width, mat[row][c])\n                        rectangles += width\n                        row += 1\n        \n        return rectangles", "class Solution:\n    def numSubmat(self, mat: List[List[int]]) -> int:\n        \n        def rectangles_staring_at(i,j):\n            res = 0\n            max_col = m\n            for x in range(i,n):\n                for y in range(j,max_col):\n                    if mat[x][y] == 1:\n                        res+=1\n                    else:\n                        max_col = y\n                        break\n            return res\n        \n        sums = [list(accumulate(row)) for row in mat]\n        print(sums)\n        ans, n, m = 0, len(mat), len(mat[0])\n        for i in range(n):\n            for j in range(m):\n                ans+=rectangles_staring_at(i,j)\n                            \n        return ans", "class Solution:\n    def numSubmat(self, mat: List[List[int]]) -> int:\n        n, m = len(mat), len(mat[0])\n\n        for i in range(n):\n            for j in range(m-1):\n                if mat[i][j+1]:\n                    mat[i][j+1] += mat[i][j]\n\n        ans = 0\n\n        for j in range(m):\n            for i in range(n):\n                add = mat[i][j]\n                for k in range(i, n):\n                    add = min(add, mat[k][j])\n                    ans += add\n\n        return ans", "class Solution:\n    def numSubmat(self, mat: List[List[int]]) -> int:\n        if not mat:return 0\n        m,n = len(mat),len(mat[0])\n        res = 0\n        #RLE - Run length encoding\n        for i in range(m):\n            for j in range(n):\n                if j:\n                    if mat[i][j]:\n                        mat[i][j] = mat[i][j-1] + 1\n                        \n        #Now,calculate all the rectangular submatrices from the RLE\n        print(mat)\n        for i in range(m):    \n            for j in range(n):\n                # (i,j) :top right of matrix\n                ans = mat[i][j]\n                for k in range(i,m):#bottom-right\n                    ans = min(ans,mat[k][j])\n                    res+= ans\n    \n        return res\n", "class Solution:\n    def numSubmat(self, mat: List[List[int]]) -> int:\n        n=len(mat)\n        m=len(mat[0])\n        ar=[]\n        for i in range(n):\n            a=[]\n            for j in range(m):\n                a.append(0)\n            ar.append(a)\n        for i in range(n):\n            c=0\n            for j in range(m-1,-1,-1):\n                if(mat[i][j]==1):\n                    c+=1\n                else:\n                    c=0\n                ar[i][j]=c\n        ans=0\n        for i in range(n):\n            for j in range(m):\n                import sys\n                x=sys.maxsize\n                for k in range(i,n):\n                    x=min(x,ar[k][j])\n                    ans+=x\n        return ans\n                    \n", "class Solution:\n    def numSubmat(self, mat: List[List[int]]) -> int:\n        \n        R =len(mat)\n        C = len(mat[0])\n        def sunmat(sr,sc):\n            maxc=C\n            count=0\n            for x in range(sr,R):\n                for y in range(sc,maxc):\n                    if mat[x][y]==1:\n                        count+=1\n                    else:\n                        maxc=y\n                        break\n            return count\n        res=0\n        for x in range(R):\n            for y in range(C):\n                if mat[x][y]==0:\n                    continue\n                res+=sunmat(x,y)\n        return res\n    \n", "class Solution:\n    def numSubmat(self, mat: List[List[int]]) -> int:\n        \n        for i in range(len(mat)):\n            for j in range(len(mat[0])):\n                if j != 0 and mat[i][j] == 1:\n                    mat[i][j] = mat[i][j-1] + 1\n                    \n        \n        res = 0\n        for i in range(len(mat)):\n            for j in range(len(mat[0])):\n                \n                ans = mat[i][j]\n                for k in range(i,len(mat)):\n                    ans = min(ans,mat[k][j])\n                    res += ans\n                    \n        return res\n                    \n", "class Solution:\n    def numSubmat(self, mat: List[List[int]]) -> int:\n        row = len(mat)\n        col = len(mat[0])\n        \n        for j in range(col-2,-1,-1):\n            for i in range(row):\n                if mat[i][j] == 1:\n                    mat[i][j] += mat[i][j+1]\n        \n        res = 0\n        for i in range(row):\n            for j in range(col):\n                MIN = float(\\\"inf\\\")\n                for k in range(i, row):\n                    MIN = min(MIN, mat[k][j])\n                    res += MIN\n        return res\n        ", "class Solution:\n    def numSubmat(self, mat: List[List[int]]) -> int:\n        R, C = len(mat), len(mat[0])\n        for r in range(R):\n            for c in range(1, C):\n                if mat[r][c]: mat[r][c] = mat[r][c-1] + 1\n        ans = 0\n        for r in range(R):\n            for c in range(C):\n                if mat[r][c]:\n                    minWidth = mat[r][c]\n                    row = r\n                    while row < R:\n                        minWidth = min(minWidth, mat[row][c])\n                        ans += minWidth\n                        row += 1 \n        return ans\n\n\n", "class Solution:\n    def numSubmat(self, mat: List[List[int]]) -> int:\n        # \u8fd9\u9053\u9898\u662f\u95ee\u6709\u591a\u5c11\u4e2asubmatrices\u6709all ones\n        # \u548c84Largest Rectangle in Histogram\u5f88\u50cf\n         \n        # \u89e3\u6cd51 - \u679a\u4e3e\u53f3\u4e0b\u89d2\n        m, n = len(mat), len(mat[0])\n        left_ones = [[0] * n for _ in range(m)]\n        for i in range(m):\n            for j in range(n):\n                if mat[i][j] == 0:\n                    left_ones[i][j] = 0\n                else:\n                    left_ones[i][j] = 1\n                    if j > 0:\n                        left_ones[i][j] += left_ones[i][j - 1]\n        \n#         res = 0\n#         for i in range(m):\n#             for j in range(n):\n#                 curr_left_ones = left_ones[i][j]\n#                 for k in range(i, -1, -1):\n#                     curr_left_ones = min(curr_left_ones, left_ones[k][j])\n#                     res += curr_left_ones\n        \n#         return res\n\n\n        ans = 0\n        for j in range(n):\n            Q = list()\n            total = 0\n            for i in range(m):\n                height = 1\n                while Q and Q[-1][0] > left_ones[i][j]:\n                    # \u5f39\u51fa\u7684\u65f6\u5019\u8981\u51cf\u53bb\u591a\u4e8e\u7684\u7b54\u6848\n                    total -= Q[-1][1] * (Q[-1][0] - left_ones[i][j])\n                    height += Q[-1][1]\n                    Q.pop()\n                total += left_ones[i][j]\n                ans += total\n                Q.append((left_ones[i][j], height))\n\n        return ans\n\n", "\\\"\\\"\\\"\nAlgo\nIn the first step, stack mat row by row to get the \\\"histogram model\\\". For example,\n\nmat = [[1,0,1],\n       [1,1,0],\n       [1,1,0]]\nbecomes\n\nmat = [[1,0,1],\n       [2,1,0],\n       [3,2,0]]\nIn the second step, traverse the stacked matrix row by row. At each position i, j, compute the number of all-1 submatrices like below.\n\nDefine 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].\n\nThe 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).\n\n* * * \n* * * * \n* * * *\n\\\"\\\"\\\"\nclass Solution:\n    def numSubmat(self, mat: List[List[int]]) -> int:\n        if not mat:return 0\n        m,n = len(mat),len(mat[0])\n        res = 0\n        #RLE - Run length encoding\n        for i in range(m):\n            for j in range(n):\n                if  j:\n                    if mat[i][j]:\n                        mat[i][j] = mat[i][j-1] + 1\n                        \n        #Now,calculate all the rectangular submatrices from the RLE\n        print(mat)\n        for i in range(m):    \n            for j in range(n):\n                # (i,j) :top right of matrix\n                ans = mat[i][j]\n                for k in range(i,m):#bottom-right\n                    ans = min(ans,mat[k][j])\n                    res+= ans\n    \n        return res", "class Solution:\n    def numSubmat(self, mat: List[List[int]]) -> int:\n        right_ct=[[0]*len(mat[0]) for _ in range(len(mat))]\n        for i in range(len(mat)):\n            ct=0\n            for j in range(len(mat[0])-1,-1,-1):\n                if mat[i][j]==1:\n                    ct+=1\n                else:\n                    ct=0\n                right_ct[i][j]=ct\n        \n        res=0\n        \n        for i in range(len(mat)):\n            for j in range(len(mat[0])):\n                right_min=float('inf')\n                for k in range(i,len(mat)):\n                    right_min=min(right_min,right_ct[k][j])\n                    res+=right_min\n        \n        return res", "class Solution:\n    def numSubmat(self, mat: List[List[int]]) -> int:\n        # \u8fd9\u9053\u9898\u662f\u95ee\u6709\u591a\u5c11\u4e2asubmatrices\u6709all ones\n        # \u548c84Largest Rectangle in Histogram\u5f88\u50cf\n         \n        # \u89e3\u6cd51 - \u679a\u4e3e\u53f3\u4e0b\u89d2, \u4f46\u662f\u8981\u5148\u51c6\u5907\u4e00\u4e2arow_left_ones\u7684\u77e9\u9635\u65b9\u4fbf\u5feb\u901f\u67e5\u627e\n        m, n = len(mat), len(mat[0])\n        row_left_ones = [[0] * n for _ in range(m)]\n        for i in range(m):\n            for j in range(n):\n                if mat[i][j] == 0:\n                    row_left_ones[i][j] = 0\n                else:\n                    row_left_ones[i][j] = 1\n                    if j > 0:\n                        row_left_ones[i][j] += row_left_ones[i][j - 1]\n        \n        res = 0\n        for i in range(m):\n            for j in range(n):\n                curr_row_left_ones = row_left_ones[i][j]\n                for k in range(i, -1, -1):\n                    curr_row_left_ones = min(curr_row_left_ones, row_left_ones[k][j])\n                    res += curr_row_left_ones\n        \n        return res\n\n        #=================\u5206\u5272\u7ebf=================#\n\n        # \u89e3\u6cd52 - \u5355\u8c03\u9012\u589e\u6808(\u4ece\u4e0a\u5f80\u4e0b\uff0c\u5373\u904d\u5386\u884ci\u7684\u987a\u5e8f)\n        res = 0\n        for j in range(n):\n            total = 0\n            # stack\u91cc\u5b58\u4e24\u4e2a\u4fe1\u606f\uff1a\n            # 1. ij\u4f4d\u7f6e\u4e0a\u7684\u5de61\u6570\u76ee(height)\n            # 2. \u5f53\u524d\u7684\u5bbd\u5ea6(\u5b9e\u9645\u4e0a\u662f\u5782\u76f4\u7684\u9ad8\u5ea6, \u6211\u4eec\u76f8\u5f53\u4e8e\u6a2a\u7740\u770b)\n            stack = []\n            for i in range(m):\n                total += left_ones[i][j]\n                width = 1\n                while stack and stack[-1][0] > left_ones[i][j]:\n                    # \u5f39\u51fa\u7684\u65f6\u5019\u8981\u51cf\u53bb\u591a\u4f59\u7684\u7b54\u6848\n                    last_ones, last_width = stack.pop()\n                    # last_ones - left_ones[i][j] \u770b\u6210\u591a\u4f59\u7684\u5217\u6570\uff08\u6bd4\u5982\u591a\u4f595\u5217\uff09\n                    # \u8fd95\u5217\u90fd\u548c\u5f53\u524d\u7684\u53f3\u4e0b\u89d2(i, j)\u80fd\u6784\u62105\u4e2a\u865a\u5047\u7684\u77e9\u5f62\n                    # \u6240\u4ee5\u8981\u51cf\u6389\n                    total -= last_width * (last_ones - left_ones[i][j])\n                    width += last_width\n                res += total\n                stack.append((left_ones[i][j], width))\n\n        return res", "class Solution:\n    def numSubmat(self, mat: List[List[int]]) -> int:\n        n = len(mat)\n        m = len(mat[0])\n        \n        ones = [[0] * (m + 1) for _ in range(n)]\n        for i in range(n):\n            for j in range(m - 1, -1, -1):\n                if mat[i][j] == 0:\n                    continue\n                ones[i][j] += 1 + ones[i][j + 1]\n        res = 0\n        for i in range(n):\n            for j in range(m):\n                width = ones[i][j]\n                for k in range(i, n):\n                    width = min(width, ones[k][j])\n                    res += width\n        return res\n", "class Solution:\n    def numSubmat(self, mat: List[List[int]]) -> int:\n        #took help from discussion\n        for i in range(len(mat)):\n            for j in range(len(mat[0])-2, -1, -1):\n                if mat[i][j] > 0:\n                    mat[i][j] += mat[i][j+1]\n                \n        ans = 0       \n        for i in range(len(mat)):\n            for j in range(len(mat[0])):\n                temp = float(\\\"inf\\\")\n                for k in range(i, len(mat)):\n                    temp = min(temp, mat[k][j])\n                    ans += temp\n                    \n        return ans", "class Solution:\n    def numSubmat(self, mat: List[List[int]]) -> int:\n        ar = [[0]*len(mat[0]) for _ in range(len(mat))]\n        for i in range(len(mat)):\n            c = 0\n            for j in range(len(mat[0])):\n                if mat[i][j]: c += 1\n                else: c = 0\n                ar[i][j] = c\n        for r in mat:\n            print(r)\n        print()\n        for r in ar:\n            print(r)\n        print()\n        ans = 0\n        for i in range(len(mat)):\n            for j in range(len(mat[0])):\n                x = float('inf')\n                for k in range(i, len(mat)):\n                    x = min(x, ar[k][j])\n                    ans += x\n        return ans\n        \n        # out = mat[0][0]\n        # mat[0][0] = [mat[0][0]]*3 # [row,col,diag]\n        # for i in range(1, len(mat)):\n        #     if mat[i][0]:\n        #         row = 1 + mat[i-1][0][0]\n        #         mat[i][0] = [row, 1, 1]\n        #         out += row\n        #     else:\n        #         mat[i][0] = [0]*3\n        # for r in mat:\n        #     print(r)\n        # print()\n        # for j in range(1, len(mat[0])):\n        #     if mat[0][j]:\n        #         col = 1 + mat[0][j-1][1]\n        #         mat[0][j] = [1, col, 1]\n        #         out += col\n        #     else:\n        #         mat[0][j] = [0]*3\n        # for r in mat:\n        #     print(r)\n        # print()\n        # for i in range(1, len(mat)):\n        #     for j in range(1, len(mat[0])):\n        #         if mat[i][j]:\n        #             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])\n        #             mat[i][j] = [row, col, diag]\n        #             out += row + col + diag - 2 # -2 to avoid triple counting\n        #         else:\n        #             mat[i][j] = [0]*3\n        # for r in mat:\n        #     print(r)\n        # return out\n", "class Solution:\n    def numSubmat(self, mat: List[List[int]]) -> int:\n        def countOneRow(a):\n            res = 0\n            length = 0\n            for el in a:\n                if el == 0:\n                    length = 0\n                else:\n                    length += 1\n\n                res += length\n            return res\n        \n        M = len(mat)\n        N = len(mat[0])\n        res = 0\n        for up in range(M):\n            h = [1] * N\n            for down in range(up, M):\n                for k in range(N):\n                    h[k] *= mat[down][k]\n                print(h)\n                res += countOneRow(h)\n        return res\n", "class Solution:\n    def numSubmat(self, mat: List[List[int]]) -> int:\n        m,n = len(mat),len(mat[0])     \n        \n        dp = [[0 for i in range(n)] for j in range(m)]\n        \n        for i in range(m):\n            count=0\n            \n            #It will find consecutive ones horizontally\n            for j in range(n-1,-1,-1):\n                if mat[i][j]:\n                    count+=1\n                else:\n                    count=0\n                dp[i][j]=count\n                \n        ans = 0\n        for i in range(m):\n            for j in range(n):\n                \n                mn = float('inf')\n                for k in range(i,m):\n                    mn = min(mn,dp[k][j])\n                    ans+=mn\n                    \n        return ans\n", "class Solution:\n    def numSubmat(self, mat: List[List[int]]) -> int:\n        \n        r=len(mat)\n        c=len(mat[0])\n        for i in range(r):\n            for j in range(c-2,-1,-1):\n                if mat[i][j]!=0:\n                    mat[i][j]=mat[i][j+1]+1\n        # print(mat)\n        count=0\n        for i in range(r):\n            for j in range(c):\n                width=mat[i][j]\n                for k in range(i,r):\n                    width=min(width,mat[k][j])\n                    count+=width\n        \n        return count\n                    \n", "class Solution:\n    def numSubmat(self, mat: List[List[int]]) -> int:\n        ret = 0\n        for i in range(len(mat)):\n            for j in range(len(mat[0])):\n                maxRight = len(mat[0])\n                for h in range(i, len(mat)):\n                    for w in range(j, maxRight):\n                        if mat[h][w] == 1:\n                            ret += 1\n                        else:\n                            maxRight = w\n                            break\n        return ret", "class Solution:\n    def numSubmat(self, mat: List[List[int]]) -> int:\n        n_row = len(mat)\n        if n_row == 0:\n            return 0\n        n_col = len(mat[0])\n        if n_col == 0:\n            return 0\n        \n        result = 0\n        hist = [0] * (n_col + 1)\n        for row in range(n_row):\n            min_hist_indices = [-1]\n            dp = [0] * (n_col + 1)\n            for col in range(n_col):\n                hist[col] = 0 if mat[row][col] == 0 else hist[col] + 1\n                \n                while hist[col] < hist[min_hist_indices[-1]]:\n                    min_hist_indices.pop()\n                \n                dp[col] = dp[min_hist_indices[-1]] + hist[col] * (col - min_hist_indices[-1])\n                \n                min_hist_indices.append(col)\n                \n            result += sum(dp)\n        return result", "class Solution:\n    def numSubmat(self, mat: List[List[int]]) -> int:\n        def num(mat,i,j):\n            result = 0\n            index_i = i\n            \n            while index_i<len(mat) and mat[index_i][j] == 1:\n                result += 1\n                index_i += 1\n            index_j = j\n            while index_j<len(mat[0]) and mat[i][index_j] == 1:\n                result += 1\n                index_j += 1\n                \n            result -= 1\n            print(result)\n            bound_i = index_i\n            bound_j = index_j\n            for row in range(i+1,bound_i):\n                for col in range(j+1,bound_j):\n                    if mat[row][col] == 1:\n                        result += 1\n                    else:\n                        bound_i = row\n                        bound_j = col\n                        break\n                        \n            return result\n        \\\"\\\"\\\"\n        if len(mat) == 0 or len(mat[0]) == 0:\n            return 0\n        \n        result = 0\n        for i in range(len(mat)):\n            for j in range(len(mat[0])):\n                if mat[i][j] == 1:\n                    n = num(mat,i,j)\n                    print(n)\n                    result += n\n        return result\n        \\\"\\\"\\\"\n        \n        \\\"\\\"\\\"\n        #O(n*n*m)\n        row = [[0]*len(mat[0]) for _ in range(len(mat))]\n        \n        for i in range(len(mat)):\n            for j in range(len(mat[0])):\n                if mat[i][j] == 1:\n                    if j == 0:\n                        row[i][j] = 1\n                    else:\n                        row[i][j] = row[i][j-1] + 1\n        result = 0\n        for i in range(len(mat)):\n            for j in range(len(mat[0])):\n                if mat[i][j] == 1:\n                    if i == 0:\n                        result += row[i][j]\n                    else:\n                        result += row[i][j]\n                        index = i - 1\n                        bound = row[i][j]\n                        while index>=0:\n                            bound = min(bound,row[index][j])\n                            if bound == 0:\n                                break\n                            result += min(row[i][j],bound)\n                            index = index - 1\n        return result\n        \\\"\\\"\\\"\n        \n        row = [[0]*len(mat[0]) for _ in range(len(mat))]\n        \n        for i in range(len(mat)):\n            for j in range(len(mat[0])):\n                if mat[i][j] == 1:\n                    if j == 0:\n                        row[i][j] = 1\n                    else:\n                        row[i][j] = row[i][j-1] + 1\n        result = 0\n        \n        for j in range(len(mat[0])):\n            stack = []\n            total = 0\n            for i in range(len(mat)):\n                height = 1\n                while len(stack)>0 and stack[-1][0]>row[i][j]:\n                    total -= stack[-1][1]*(stack[-1][0] - row[i][j])\n                    height += stack[-1][1]\n                    stack.pop()\n                total += row[i][j]\n                result += total\n                stack.append([row[i][j],height])\n        return result\n        \n        \n        \n        \n        \n        ", "class Solution:\n    def numSubmat(self, mat: List[List[int]]) -> int:\n        total_sub_matrix = 0\n        for row in range(len(mat)):\n            for col in range(len(mat[0])):\n\n                if mat[row][col] == 1:\n\n                    max_col = len(mat[0])\n                    for sub_row in range(row, len(mat)):\n                        for sub_col in range(col, max_col):\n                            if mat[sub_row][sub_col] == 0:\n                                max_col = sub_col\n                                break\n                            \n                            total_sub_matrix += 1\n        return total_sub_matrix", "class Solution:\n    def numSubmat(self, mat: List[List[int]]) -> int:\n        M = len(mat)\n        N = len(mat[0])\n        \n        res = 0\n        \n        for i in range(M):\n            r = [1] * N\n            for j in range(i, M):\n                r = [r[k] & mat[j][k] for k in range(N)]\n                res += self.countOneRow(r)\n        return res\n    \n    def countOneRow(self, r):\n        res = length = 0\n        for i, x in enumerate(r):\n            length = 0 if x == 0 else length + 1\n            res += length\n        return res", "class Solution:\n    def numSubmat(self, mat):\n        m, n = len(mat), len(mat[0])\n        dp = [[None for i in range(n)] for j in range(m)]\n        \n        for i in range(m):\n            count = 0\n            \n            for j in range(n-1, -1, -1):\n                if mat[i][j]:\n                    count += 1\n                else:\n                    count = 0\n                dp[i][j] = count\n        \n        res = 0\n        for i in range(m):\n            for j in range(n):\n                min_val = float('inf')\n                \n                for k in range(i, m):\n                    min_val = min(min_val, dp[k][j])\n                    res += min_val\n                    \n        return res", "class Solution:\n    def numSubmat(self, mat: List[List[int]]) -> int:\n        n = len(mat); m = len(mat[0])\n        arr = mat.copy()\n        for i in range(n):\n            c = 0\n            for j in range(m):\n                if mat[i][j]:\n                    c += 1\n                else:\n                    c = 0\n                arr[i][j] = c\n        \n        ans = 0\n        for i in range(n):\n            for j in range(m):\n                x = sys.maxsize\n                for k in range(i, n):\n                    x = min(x, arr[k][j])\n                    ans += x\n        \n        return ans", "class Solution:\n    def numSubmat(self, mat: List[List[int]]) -> int:\n        \n        m,n = len(mat), len(mat[0])\n\n        for i in range(m):\n            for j in range(n-2,-1,-1):\n                if mat[i][j] == 1:\n                    mat[i][j]+= mat[i][j+1]\n\n        c = 0\n        for i in range(m):\n            for j in range(n):\n                min_ = mat[i][j]\n                for d in range(i,m):\n                    if not mat[i][j]:\n                        continue\n                    min_ = min(min_, mat[d][j])\n                    c = c + min_\n\n        return (c)\n\n", "from collections import defaultdict\n\nclass Solution:\n    def numSubmat(self, mat: List[List[int]]) -> int:\n        \n        \n        n,m=len(mat),len(mat[0])\n        cnt=0\n        def count(arr):\n            cnt=[0]*len(arr)\n            if arr[0]==1:\n                cnt[0]=1\n            for i in range(1,len(arr)):\n                if arr[i]==arr[i-1]==1:\n                    cnt[i]=cnt[i-1]+1\n                elif arr[i]==1:\n                    cnt[i]=1\n                else:\n                    cnt[i]=0\n            return sum(cnt)\n                \n        ans=0\n        \n        for left in range(m):\n            c=[1 for i in range(n)]\n            for right in range(left,m):                \n                for i in range(n):\n                    c[i]=c[i] and mat[i][right]\n                ans+=count(c)\n                  \n        return ans\n                    \n                \n                \n", "class Solution:\n    def numSubmat(self, mat: List[List[int]]) -> int:\n        n, m = len(mat), len(mat[0])\n        accs = []\n        \n        for i in range(n):\n            acc = [0]\n            \n            for j in range(m):\n                acc.append(acc[-1]+mat[i][j])\n            \n            accs.append(acc)\n        \n        ans = 0\n        \n        for i in range(m):\n            for j in range(i, m):\n                cnt = 0\n                \n                for k in range(n):\n                    if accs[k][j+1]-accs[k][i]==j-i+1:\n                        cnt += 1\n                    else:\n                        ans += cnt*(cnt+1)//2\n                        cnt = 0\n        \n                ans += cnt*(cnt+1)//2\n        \n        return ans", "class Solution:\n    def numSubmat(self, mat: List[List[int]]) -> int:      \n        mat = [[0] + row for row in mat]\n        m, n = len(mat), len(mat[0])\n        result = 0\n        for i, row in enumerate(mat):\n            stack = []\n            count = [0] * n\n            for j in range(n):\n                if row[j] and i:\n                    row[j] += mat[i - 1][j]\n                while stack and row[stack[-1]] > row[j]:\n                    stack.pop()\n                if j and row[j]:\n                    count[j] = count[stack[-1]] + row[j] * (j - stack[-1])\n                    result += count[j]\n                stack.append(j)\n        return result\n        \n        \n        \n#         m, n = len(mat), len(mat[0])\n#         for i in range(1, m):\n#             for j in range(n):\n#                 if mat[i][j]:\n#                     mat[i][j] += mat[i - 1][j]\n#         result = 0\n#         for i in range(m):\n#             for k in range(i, m):\n#                 height = k - i + 1\n#                 width = 0\n#                 for j in range(n):\n#                     if mat[k][j] >= height:\n#                         width += 1\n#                         result += width\n#                     else:\n#                         width = 0\n#         return result\n", "class Solution:\n    def numSubmat(self, mat: List[List[int]]) -> int:\n        m, n = len(mat), len(mat[0])\n        count = 0\n        for left in range(n):\n            row_sums = [0 for _ in range(m)]\n            for right in range(left, n):\n                consec_count = 0\n                width = right - left + 1\n                for bottom in range(m):\n                    row_sums[bottom] += mat[bottom][right]\n                    if row_sums[bottom] != width:\n                        consec_count = 0\n                    else:\n                        consec_count += 1\n                        count += consec_count\n        return count\n\n", "class Solution:\n    def numSubmat(self, mat: List[List[int]]) -> int:\n        ans = 0\n        N = len(mat)\n        M = len(mat[0])\n        row = 0 \n        col = 0\n        for row in range(N):\n            for col in range(M):\n                if mat[row][col] == 0:\n                    continue\n                else:\n                    i = row\n                    j = col\n                    n = N \n                    while j < M:\n                        if mat[i][j] == 0 or i == n:\n                            n = i\n                            i = row\n                            j += 1\n                        elif i+1 == N:\n                            i = row\n                            j += 1\n                            ans += 1\n                        else:\n                            ans += 1\n                            i += 1\n        return ans\n", "class Solution:\n    def numSubmat(self, mat: List[List[int]]) -> int:\n        n = len(mat)\n        m = len(mat[0])\n        cumones = [[0]*m for x in range(n)]\n        for i in range(n):\n            for j in range(m-1, -1, -1):\n                if mat[i][j] == 1:\n                    cumones[i][j] = 1+(cumones[i][j+1] if j < m-1 else 0)\n        ct = 0\n        for i in range(n):\n            for j in range(m):\n                minw = sys.maxsize\n                for k in range(i,n):\n                    if mat[i][j] == 1:\n                        minw = min(minw, cumones[k][j])\n                        ct += minw\n        return ct", "class Solution:\n    def numSubmat(self, mat: List[List[int]]) -> int:\n        # O(m ^ 2 * n); Space: O(mn)\n        if not mat:\n            return 0\n        \n        m, n = len(mat), len(mat[0])\n        \n        dp = [[0] * (n + 1) for _ in range(m + 1)]\n        \n        res = 0\n        for i in range(1, m + 1):\n            for j in range(1, n + 1):\n                if mat[i - 1][j - 1]:\n                    dp[i][j] = dp[i][j - 1] + 1 # walk left\n                    res += dp[i][j]\n                    # walk above\n                    min_ones = dp[i][j]\n                    for k in range(i - 1, -1, -1):\n                        min_ones = min(min_ones, dp[k][j])\n                        res += min_ones\n        return res", "class Solution:\n    def numSubmat(self, mat: List[List[int]]) -> int:\n        M, N = len(mat), len(mat[0])\n        res = 0\n        for up in range(M):\n            h = [1 for i in range(N)]\n            for down in range(up, M):\n                for col in range(N):\n                    h[col] &= mat[down][col]\n                res += self.oneArray(h)\n        return res\n                \n    \n    def oneArray(self, arr):\n        res = length = 0\n        for a in arr:\n            length = 0 if a == 0 else length + 1\n            res += length\n        return res", "class Solution:\n    def numSubmat(self, mat: List[List[int]]) -> int:\n        m = len(mat)\n        n = len(mat[0])\n        pre = [[0]*(n+1) for _ in range(m)]\n        \n        for row in range(m):\n            for col in range(1, n+1):\n                pre[row][col] = mat[row][col-1] + pre[row][col-1]\n        \n        ans = 0\n        for col1 in range(n):\n            for col2 in range(col1+1, n+1):\n                local_ans = 0\n                curr_stack = 0\n                for row in range(m):\n                    if pre[row][col2] - pre[row][col1] == col2-col1:\n                        curr_stack += 1\n                        local_ans += curr_stack\n                    else:\n                        curr_stack = 0\n                ans += local_ans\n        return ans", "class Solution:\n    def numSubmat(self, A: List[List[int]]) -> int:\n        m, n = len(A), len(A[0])\n        \n        res = 0\n        \n        for i in range(m):\n            r = [1] * n\n            for j in range(i, m):\n                for k in range(n):\n                    r[k] &= A[j][k]\n                    \n                res += self.count(r)\n                \n        return res\n    \n    def count(self, r):\n        res = head = 0\n        for n in r:\n            head = head + 1 if n else 0\n            res += head\n        return res", "class Solution:\n    def numSubmat(self, mat: List[List[int]]) -> int:\n        ans = 0\n        for i in range(len(mat)):\n            for j in range(len(mat[0])):\n                row,col = 0,0\n                if mat[i][j] == 1:\n                    while row<len(mat)-i and mat[i+row][j] == 1:\n                        row += 1\n                    while col<len(mat[0])-j and mat[i][j+col] == 1:\n                        col += 1\n                    cnt,col_min = 0, col\n                    for ii in range(row):\n                        for jj in range(min(col_min,col)):\n                            if mat[i+ii][j+jj]==1:\n                                cnt += 1\n                            else:\n                                col_min = jj\n                                break\n                    print((i,j,cnt))\n                    ans += cnt\n        return ans\n", "class Solution:\n    def numSubmat(self, mat: List[List[int]]) -> int:\n        ans = 0\n        N, M = len(mat), len(mat[0])\n        for i in range(N):\n            mask  = mat[i]\n            for j in range(i, N):\n                if j > i:\n                    mask = [int(i&j) for i, j in zip(mask, mat[j])]\n                cnt = 0\n                for k in mask:\n                    if k == 1:\n                        cnt += 1\n                    else:\n                        ans += cnt * (cnt+1) // 2\n                        cnt = 0\n                ans += cnt * (cnt+1) // 2\n        return ans", "class Solution:\n    def numSubmat(self, mat: List[List[int]]) -> int:\n        ans = 0\n        N, M = len(mat), len(mat[0])\n        for i in range(N):\n            mask  = mat[i]\n            for j in range(i, N):\n                if j > i:\n                    mask = [int(i&j) for i, j in zip(mask, mat[j])]\n                cnt = 0\n                for k in mask:\n                    if k == 1:\n                        cnt += 1\n                    else:\n                        ans += cnt * (cnt+1) // 2\n                        cnt = 0\n                ans += cnt * (cnt+1) // 2\n        return ans\n\n\n", "class Solution:\n    def numSubmat(self, mat):\n        if not mat:\n            return 0\n        row, col = len(mat), len(mat[0])\n        for r in range(row):\n            for c in range(col):\n                if mat[r][c] >= 1 and r:\n                    mat[r][c] += mat[r-1][c] \n        answer = 0\n        for row in mat:\n            stack = [-1]\n            num_submatrices = 0 \n            for i, num in enumerate(row):\n                while stack[-1] != -1 and num <= row[stack[-1]]:\n                    larger_num_idx = stack.pop()\n                    num_submatrices -= row[larger_num_idx] * (larger_num_idx-stack[-1])\n                num_submatrices += num * (i-stack[-1])\n                answer += num_submatrices\n                stack.append(i)\n        return answer \n", "class Solution:\n    # This idea is to conver the problem from the 2d version to 1d version\n    def numSubmat(self, mat: List[List[int]]) -> int:\n        res = 0\n        m, n = len(mat), len(mat[0])\n        \n        def v1d(h):\n            ans = 0\n            length = 0\n            for v in h:\n                length = length + 1 if v else 0\n                ans += length\n            return ans\n\n        for i in range(m):\n            h = [1]*n\n            for idown in range(i, m):\n                for j in range(n):\n                    h[j] &= mat[idown][j]\n                res += v1d(h)\n        return res\n            \n        \n        \n        \n        \n    # this method start with 1x1, and then try to extend a small matrix\n    # to bigger matrix by extending row and collum by 1.\n    # The problem is that, it will check a lot of duplicates\n    # TEL\n    def numSubmat_dp_style(self, mat: List[List[int]]) -> int:\n        allones = set()\n        m, n = len(mat), len(mat[0])\n        q = collections.deque()\n        for i, j in itertools.product(range(m), range(n)):\n            if mat[i][j]:\n                q.append((i, j, 1, 1))\n                allones.add((i, j, 1, 1))\n        \n        while q:\n            i, j, r, c = q.popleft()\n            # check r+1, c+1\n            if i+r < m and (i+r, j, 1, c) in allones:\n                q.append((i, j, r+1, c))\n                allones.add((i, j, r+1, c))\n            \n            if j + c < n and (i, j+c, r, 1) in allones:\n                q.append((i, j, r, c+1))\n                allones.add((i, j, r, c+1))\n        return len(allones)", "class Solution:\n    def numSubmat(self, mat: List[List[int]]) -> int:\n        \n        m = len(mat)\n        if not m: return 0\n        n = len(mat[0])\n        \n        dp = [[0] * n for _ in range(m)]\n        \n        for i in range(m):\n            for j in range(n):\n                if mat[i][j] == 1:\n                    if j == 0:\n                        dp[i][j] = 1\n                    else:\n                        dp[i][j] = dp[i][j-1] + 1\n        res = 0    \n        for i in range(m):\n            for j in range(n):\n                if mat[i][j] == 0:\n                    continue\n                row = i\n                minWidth =math.inf\n                while row >= 0 and mat[i][j]:\n                    minWidth = min(minWidth, dp[row][j])\n                    res += minWidth\n                    row -= 1\n        return res\n", "class Solution:\n    def numSubmat(self, mat: List[List[int]]) -> int:\n        n = len(mat)\n        m = len(mat[0])\n        ar = [[0 for j in range(m)]for i in range(n)]\n        c = 0\n        for i in range(n):\n            c = 0 \n            for j in range(m-1,-1,-1):\n                if mat[i][j] == 1:\n                    c += 1\n                else:\n                    c = 0\n                ar[i][j] = c\n        \n        ans = 0\n        for i in range(n):\n            for j in range(m):\n                x = float('inf')\n                for k in range(i,n):\n                    x = min(x,ar[k][j])\n                    ans += x\n        \n        return ans", "class Solution:\n    def numSubmat(self, mat: List[List[int]]) -> int:\n        M, N = len(mat), len(mat[0])\n        res = 0\n        for top in range(M):\n            h = [1 for _ in range(N)]\n            for bottom in range(top, M):\n                for j in range(N):\n                    h[j] &= mat[bottom][j]\n                res += self.count1D(h)\n        return res\n    \n    def count1D(self, array):\n        res, length = 0, 0\n        for i in range(len(array)):\n            if array[i] == 0:\n                length = 0\n            else:\n                length += 1\n            res += length\n        return res", "class Solution:\n    def numSubmat(self, mat: List[List[int]]) -> int:\n        r, c = len(mat), len(mat[0])\n        res = 0\n        dp = [[0] * (c + 1) for _ in range(r + 1)]\n        for i in range(1, r + 1):\n            for j in range(1, c + 1):\n                if mat[i - 1][j - 1]:\n                    dp[i][j] = dp[i][j - 1] + 1\n                    res += dp[i][j]\n                    min_ones = dp[i][j]\n                    for k in range(i - 1, -1, -1):\n                        min_ones = min(min_ones, dp[k][j])\n                        res += min_ones\n        return res\n", "#https://www.youtube.com/watch?v=8HYXkNB39KA\n#https://www.youtube.com/watch?v=hrd-MEcZkOI&feature=youtu.be\nclass Solution:\n    def numSubmat(self, mat: List[List[int]]) -> int:\n        rows=len(mat)\n        cols=len(mat[0])\n        for r in range(rows):\n            for c in range(cols):\n                if mat[r][c]:\n                    if c>0:\n                        mat[r][c]=mat[r][c-1]+1\n        \n        submatrices=0\n        for r in range(rows):\n            for c in range(cols):\n                if mat[r][c]:\n                    row=r\n                    min_value=mat[r][c]\n                    while row<rows and mat[r][c]:\n                        min_value=min(min_value,mat[row][c])\n                        submatrices+=min_value\n                        row+=1\n        return submatrices              \n                        \n        \n            \n             \n                    \n\n        \n                     \n        \n", "class Solution:\n    def helper(self, mat, a, b):\n        N = len(mat)\n        M = len(mat[0])\n        \n        bound = M\n        count = 0\n        \n        for r in range(a, N):\n            for c in range(b, bound):                \n                if mat[r][c] == 1: \n                    if (a,b) == (0,0):\n                        print(\\\"!! rc\\\", r,c)\n                    count += 1\n                else:\n                    bound = c\n                    break\n        return count\n                \n        \n        \n    def numSubmat(self, mat: List[List[int]]) -> int:\n        N = len(mat)\n        if N == 0: return 0\n        M = len(mat[0])\n        count = 0 \n        \n        for r in range(N):\n            for c in range(M):\n                out = self.helper(mat, r, c)\n                print(\\\"!\\\", r, c, out)\n                count += out\n        \n        return count", "class Solution:\n    def numSubmat(self, A: List[List[int]]) -> int:\n        r = len(A)\n        c = len(A[0])\n        dp = [[0]*(c+1) for _ in range(r+1)]\n        for i in range(r):\n            dp[i][0] = 0\n            for j in range(c):\n                dp[i][j+1] = dp[i][j] + A[i][j]\n        ans = 0\n        for lhs in range(c):\n            for rhs in range(lhs, c):\n                amt = 0\n                for i in range(r):\n                    if dp[i][rhs+1] - dp[i][lhs] == rhs-lhs+1:\n                        amt += 1 \n                    else:\n                        amt = 0\n                    ans += amt\n        return ans\n        \n        \n        \n\\\"\\\"\\\"\nFor each row i, create an array nums where:\n\nmat[i][j] == 0 then nums[j] = 0 else nums[j] = nums[j-1] + 1\n\nIn row i, the number of rectangles between column j and k(inclusive) and ends in row i\nis equal to sum(min(nums[j,...,idx])) where idx go from j to k\n\n\nin row i the number of rectangles between column j and k that ends in row i is equal to\nsum ( min ( row[j:idx+1])) for idx in range(j, k)\n\nexpected solution is O(n*3)\n\\\"\\\"\\\"", "class Solution:\n    def numSubmat(self, mat: List[List[int]]) -> int:\n        row = len(mat)\n        col = len(mat[0])\n        \n        dp = [[None]*col for _ in range(row)]\n        \n        for i in range(row):\n            count = 0\n            for j in range(col):\n                if mat[i][j] == 1:\n                    count += 1\n                else:\n                    count = 0\n                dp[i][j] = count\n        \n        res = 0\n        for i in range(row):\n            for j in range(col):\n                mn = float('inf')\n                for k in range(i, row):\n                    mn = min(mn, dp[k][j])\n                    res += mn\n        return res\n", "class Solution:\n    def numSubmat(self, A: List[List[int]]) -> int:\n        m, n = len(A), len(A[0])\n        h = [0] * n\n        res = 0\n        \n        for i in range(m):\n            \n            stk = []\n            psum = [0] * n\n\n            for j in range(n):\n                h[j] = h[j] + 1 if A[i][j] else 0\n                \n                while stk and h[stk[-1]] >= h[j]: stk.pop()\n                    \n                k = stk[-1] if stk else -1\n                ksum = psum[k] if stk else 0\n                \n                psum[j] = ksum + h[j] * (j - k)\n                \n                stk.append(j)\n                \n            res += sum(psum)\n                \n        return res", "class Solution:\n    def numSubmat(self, mat: List[List[int]]) -> int:\n        r = len(mat)\n        c = len(mat[0])\n\n        for i in range(r): \n            for j in range(c-2,-1,-1):\n                if mat[i][j] == 1:\n                    if j < (c-1):\n                        mat[i][j] += mat[i][j+1]\n        \n        res = 0\n        print(mat)\n        \n        for i in range(r):\n            for j in range(c):\n                m = float('inf')\n                for k in range(i,r):\n                    m = min(m, mat[k][j])\n                    res += m\n        \n        return res", "class Solution:\n    def numSubmat(self, mat: List[List[int]]) -> int:\n        m = len(mat)\n        n = len(mat[0])\n        \n        ans = 0\n        for i1 in range(m):\n            dp = [0] * n\n            for i2 in range(i1, m):\n                for j in range(n):\n                    dp[j] += mat[i2][j]\n                \n                l = 0\n                j = 0\n                while j < n:\n                    if dp[j] == i2 - i1 + 1:\n                        l += 1\n                    else:\n                        ans += l * (l + 1) // 2\n                        l = 0\n                    \n                    j += 1\n                \n                if l > 0:\n                    ans += l * (l + 1) // 2\n        \n        return ans", "class Solution:\n    def numSubmat(self, mat: List[List[int]]) -> int:\n        m = len(mat)\n        n = len(mat[0])\n        \n        \n        def count_submatrices(r, c):\n            count = 0\n            bound = n\n            for i in range(r, m):\n                for j in range(c, bound):\n                    if j >= bound:\n                        continue\n                    elif mat[i][j] == 1:\n                        count += 1\n                    else:\n                        bound = j\n            return count\n            \n        # return count_submatrices(0, 0)\n        total_count  = 0\n        for r, row in enumerate(mat):\n            for c, cell in enumerate(row):\n                total_count += count_submatrices(r, c)\n\n        return total_count", "class Solution:\n    def numSubmat(self, mat: List[List[int]]) -> int:\n        def counts(nums):\n            endhere = [0]*len(nums)\n            st = []\n            for i, num in enumerate(nums):\n                while st and nums[st[-1]] >= num:\n                    st.pop()\n                if not st:\n                    endhere[i] = num * (i + 1)\n                else:\n                    prev_idx = st[-1]\n                    endhere[i] = endhere[prev_idx]\n                    endhere[i] += num*(i - prev_idx)\n                st.append(i)\n            return sum(endhere)\n        rows = mat[0][:]\n        ans = counts(rows[:])\n        # print(ans)\n        for i in range(1, len(mat)):\n            for j in range(len(mat[0])):\n                if mat[i][j] == 1:\n                    rows[j] += 1\n                else:\n                    rows[j] = 0\n            # print(rows)\n            ans += counts(rows[:])\n            # print(ans)\n        return ans\n                    \n", "class Solution:\n    def numSubmat(self, mat: List[List[int]]) -> int:\n        m, n = len(mat), len(mat[0])\n        \n        #precipitate mat to histogram \n        for i in range(m):\n            for j in range(n):\n                if mat[i][j] and i > 0: \n                    mat[i][j] += mat[i-1][j] #histogram \n        \n        ans = 0\n        for i in range(m):\n            stack = [] #mono-stack of indices of non-decreasing height\n            cnt = 0\n            for j in range(n):\n                while stack and mat[i][stack[-1]] > mat[i][j]: \n                    jj = stack.pop()                          #start\n                    kk = stack[-1] if stack else -1           #end\n                    cnt -= (mat[i][jj] - mat[i][j])*(jj - kk) #adjust to reflect lower height\n\n                cnt += mat[i][j] #count submatrices bottom-right at (i, j)\n                ans += cnt\n                stack.append(j)\n\n        return ans", "class Solution:\n    def numSubmat(self, mat: List[List[int]]) -> int:\n        m = len(mat)\n        n = len(mat[0])\n        tot = 0\n        for i in range(m):\n            prev = []\n            for j in range(n):\n                if not mat[i][j]:\n                    prev = []\n                    continue\n                if i > 0:\n                    mat[i][j] += mat[i - 1][j]\n                h = mat[i][j]\n                tot += h\n                for p in range(len(prev) - 1, -1, -1):\n                    if prev[p] > h:\n                        prev[p] = h\n                    tot += prev[p]\n                prev.append(h)\n        return tot\n", "class Solution:\n    def helper(self, heights, n):\n        stack = []\n        res = [0] * n\n        for i in range(n):\n            while stack and heights[stack[-1]] >= heights[i]:\n                stack.pop()\n            if stack:\n                prev = stack[-1]\n                res[i] = res[prev] + heights[i] * (i - prev)\n            else:\n                res[i] = heights[i] * (i + 1)\n            stack.append(i)\n        return sum(res)\n    def numSubmat(self, mat: List[List[int]]) -> int:\n        m, n = len(mat), len(mat[0])\n        heights = [[0] * n for _ in range(m)]\n        res = 0\n        for j in range(n):\n            if mat[0][j] == 1:\n                heights[0][j] = 1\n        for i in range(1, m):\n            for j in range(n):\n                if mat[i][j] == 1:\n                    heights[i][j] = heights[i-1][j] + 1\n        for i in range(m):\n            res += self.helper(heights[i], n)\n        return res", "class Solution:\n  #  def helper(self, l):\n  #      num = 0\n  #      ct = 0\n  #      for j in range(len(l)):\n  #          if l[j] == 1:\n  #              ct += 1\n  #          else:\n  #              ct = 0\n  #          num += ct\n  #      \n  #      return num\n  #  \n  #\n  #  def numSubmat(self, mat: List[List[int]]) -> int:\n  #      m = len(mat)\n  #      n = len(mat[0])\n  #      tot_sum = 0\n  #      for i1 in range(m):\n  #          l = [1]*n\n  #          for i2 in range(i1, m):\n  #              for j in range(n):\n  #                  l[j] &= mat[i2][j]\n  #              tot_sum += self.helper(l)\n  #              \n  #      return tot_sum\n  #  \n    \n    def helper(self, arr):\n        tracker = [0] * len(arr)\n        stack = []\n        \n        for i in range(len(arr)):\n            while stack and arr[stack[-1]] >= arr[i]:\n                stack.pop()\n            if stack:\n                tracker[i] = tracker[stack[-1]]\n                tracker[i] += arr[i] * (i - stack[-1])\n            else:\n                tracker[i] = arr[i] * (i + 1)\n            stack.append(i)\n        \n        return sum(tracker)\n    \n    def numSubmat(self, mat: List[List[int]]) -> int:\n        m = len(mat)\n        n = len(mat[0])\n        column_track = [0] * n\n        res = 0\n        \n        for i in range(m):\n            for j in range(n):\n                column_track[j] = 0 if mat[i][j] == 0 else column_track[j] + 1\n            res += self.helper(column_track)\n        \n        return res\n            \n    \n        \n            \n", "class Solution:\n    def numSubmat(self, mat: List[List[int]]) -> int:\n        m,n,res = len(mat), len(mat[0]),0\n        histogram = [0] * (n+1)\n        for i in range(m):\n            stack,dp = [-1], [0]*(n+1)\n            for j in range(n):\n                if mat[i][j] == 0:\n                    histogram[j] = 0\n                else:\n                    histogram[j] += 1\n            \n                while histogram[j] < histogram[stack[-1]]:\n                    #print(stack)\n                    stack.pop()\n                    #print(stack)\n\n                #print(stack)\n                dp[j] = dp[stack[-1]] + histogram[j] * (j-stack[-1])\n                stack.append(j)\n                \n            res += sum(dp)\n            \n        return res", "class Solution:\n    def numSubmat(self, mat: List[List[int]]) -> int:\n        def pom(tab):\n            stack = []\n            sums = [0] * len(tab)\n            for i in range(len(tab)):\n                while len(stack) > 0 and tab[stack[-1]] > tab[i]:\n                    stack.pop()\n                if len(stack) == 0:\n                    sums[i] = (i + 1) * tab[i]\n                else:\n                    sums[i] = sums[stack[-1]] + tab[i] * (i - stack[-1])\n                stack.append(i)\n\n            return sum(sums)\n        \n        n_rows = len(mat)\n        n_cols = len(mat[0])\n        h = [0] * n_cols\n        res = 0\n        for row in mat:\n            for i in range(len(row)):\n                if row[i] == 1:\n                    h[i] += 1\n                else:\n                    h[i] = 0\n            res += pom(h)\n        \n        return res", "class Solution:\n    def numSubmat(self, mat: List[List[int]]) -> int:\n        m, n = len(mat), len(mat[0])\n        \n        #precipitate mat to histogram \n        for i in range(m):\n            for j in range(n):\n                if mat[i][j] and i > 0: \n                    mat[i][j] += mat[i-1][j] #histogram \n        \n        ans = 0\n        for i in range(m):\n            stack = [] #mono-stack of indices of non-decreasing height\n            cnt = 0\n            for j in range(n):\n                while stack and mat[i][stack[-1]] > mat[i][j]: \n                    jj = stack.pop()                          #start\n                    kk = stack[-1] if stack else -1           #end\n                    cnt -= (mat[i][jj] - mat[i][j])*(jj - kk) #adjust to reflect lower height\n\n                cnt += mat[i][j] #count submatrices bottom-right at (i, j)\n                ans += cnt\n                stack.append(j)\n\n        return ans\n", "class Solution:\n    def numSubmat(self, mat: List[List[int]]) -> int:\n        M, N = len(mat), len(mat[0])\n        for i in range(1, M):\n            for j in range(N):\n                if mat[i][j]:\n                    mat[i][j] += mat[i-1][j]\n        \n        # 3, 5, 2, 1, 0, 4\n        # count[0] = 3 * (0 + 1)\n        # count[1] = 5 * (1 - 0) + count[0]\n        # count[2] = 2 * (2 + 1)\n        # count[3] = 1 * (3 + 1)\n        \n        result = 0\n        for row in mat:\n            count = [0] * N\n            stk = []\n            for i, e in enumerate(row):\n                while stk and row[stk[-1]] >= e:\n                    stk.pop()\n                \n                if stk:\n                    count[i] = count[stk[-1]] + e * (i - stk[-1])\n                else:\n                    count[i] = e * (i + 1)\n                \n                stk.append(i)\n            result += sum(count)\n        return result", "class Solution:\n    def numSubmat(self, mat: List[List[int]]) -> int:\n        if not mat:\n            return 0\n        m = len(mat)\n        n = len(mat[0])\n        \n        for y in range(m):\n            for x in range(n):\n                if mat[y][x] and y > 0:\n                    mat[y][x]  += mat[y-1][x]\n                    \n        ans = 0\n        for y in range(m):\n            stack = []\n            cnt = 0\n            for x in range(n):\n                # stack is the last element \n                while stack and mat[y][stack[-1]] > mat[y][x]:\n                    #########  remove the top row from the next calculation of adding cnt \n                    # * * * \n                    #\n                    # * * * *\n                    # * * * *\n                    \n                    prev_hist_end = stack.pop()\n                    prev_hist_start = stack[-1] if stack else -1\n                    # difference in historgram height * width\n                    cnt -= (prev_hist_end - prev_hist_start)*(mat[y][prev_hist_end] - mat[y][x])\n                cnt += mat[y][x]\n                ans += cnt\n                stack.append(x)\n                \n        return ans", "class Solution:\n    def numSubmat(self, mat: List[List[int]]) -> int:\n        if not mat: return 0\n        m, n = len(mat), len(mat[0])\n        ans = 0\n        colCount = [0] * n\n        for i in range(m):\n            rowCount = 0\n            colCount1 = [0] * n\n            for j in range(n):\n                if mat[i][j]:\n                    rowCount += 1\n                    colCount1[j] = colCount[j] + 1\n                    minColCount = math.inf\n                    for k in range(j, j - rowCount, -1):\n                        minColCount = min(minColCount, colCount1[k])\n                        ans += minColCount\n                else:\n                    colCount1[j] = 0\n                    rowCount = 0\n            colCount = colCount1\n        return ans\n", "class Solution:\n#     https://leetcode.com/problems/count-submatrices-with-all-ones/discuss/721999/Python3-O(MN)-histogram-model\n    # Should pay more attention to this one\n    # Histogram model. First, stack all the rows, (prefix sum vertically)\n    # And then use a non-decreasing stack for each row\n    # Cumulate count to res, unless lower height appears, adjust the height\n    # Using non-decreasing stack and cumulative, each time, you can add current height to each of the previous same row possibility \n    # We rule out the non-continuous\n    def numSubmat(self, mat: List[List[int]]) -> int:\n        m,n = len(mat),len(mat[0])\n        for r in range(m):\n            for c in range(n):\n                if mat[r][c] and r > 0:\n                    mat[r][c] += mat[r-1][c]\n        res = 0\n        for r in range(m):\n            count = 0\n            stack = []\n            for c in range(n):\n                while stack and mat[r][stack[-1]] > mat[r][c]:\n                    j = stack.pop()\n                    w = stack[-1] if stack else -1\n                    count -= (mat[r][j]-mat[r][c])*(j-w)\n                    \n                count += mat[r][c]\n                res += count\n                stack.append(c)\n        return res\n                \n\n            \n", "class Solution:\n    def numSubmat(self, mat: List[List[int]]) -> int:\n        \n        ans = 0\n        M = len(mat)\n        if M==0:\n            return 0\n        N = len(mat[0])\n        \n        count = [0 for _ in range(N)]\n        ans = 0\n        for i in range(M):\n            rowcount = 0\n            for j in range(N):\n                if mat[i][j]==1:\n                    count[j] += 1\n                    rowcount += 1\n                    \n                    minV = 1<<30\n                    for k in range(j, j-rowcount, -1):\n                        minV=min(minV, count[k])\n                        ans += minV\n                    \n                else:\n                    rowcount = 0\n                    count[j] = 0\n                    \n        return ans\n                    \n\n                \n", "class Solution:\n    def numSubmat1(self, mat: List[List[int]]) -> int:\n        m,n,res=len(mat),len(mat[0]),0\n        histogram=[0]*(n)\n        for i in range(m):\n            stack,dp=[],[0]*(n)\n            for j in range(n):\n                histogram[j]=0 if mat[i][j]==0 else histogram[j]+1\n                while stack and histogram[j]<histogram[stack[-1]]: #increasing stack\n                    stack.pop()\n                if stack:\n                    dp[j]=dp[stack[-1]]+histogram[j]*(j-stack[-1]) # Important!!\n                else:\n                    dp[j] = histogram[j]*(j+1)\n                stack.append(j)\n            res+=sum(dp)\n            print (res)\n        return res\n    def numSubmat(self, mat: List[List[int]]) -> int:\n        m,n = len(mat),len(mat[0])\n        \n        count = 0 \n        hist = [0]*(n)\n        for i in range(m):\n            \n            dp  = [0]*n\n            for j in range(n):\n                if mat[i][j] == 1:\n                    hist[j] +=1\n                else:\n                    hist[j] = 0\n            stack = []\n            for j,h in enumerate(hist):\n                while stack and hist[stack[-1]]  >= h:\n                    stack.pop()\n                if stack:\n                    dp[j]=dp[stack[-1]]+hist[j]*(j-stack[-1]) \n                else:\n                    dp[j] = hist[j]*(j+1)\n                stack.append(j)\n            count += sum(dp)\n            print (count)\n        return count ", "class Solution:\n    def numSubmat(self, mat: List[List[int]]) -> int:\n        \n        lim1 = len(mat)\n        lim2 = len(mat[0])\n        \n        hz = [[0 for j in range(0,lim2)] for i in range(0,lim1)]\n        \n        t = 0\n        for i in range(lim1-1,-1,-1):\n            for j in range(lim2-1,-1,-1):\n                if mat[i][j]!=0:\n                    if j<lim2-1:\n                        hz[i][j]+=hz[i][j+1]+1\n                    else:\n                        hz[i][j]=1\n        \n        vt = [[0 for j in range(0,lim2)] for i in range(0,lim1)]\n        \n        for i in range(0,lim1):\n            for j in range(0,lim2):\n                if hz[i][j]!=0:\n                    mn = 99999999999\n                    for k in range(i,lim1):\n                        if hz[k][j]==0:\n                            break\n                        else:\n                            if hz[k][j]<mn:mn = hz[k][j]\n                    \n                        t+=mn\n        \n        return t\n        \n", "class Solution:\n    def numSubmat(self, mat: List[List[int]]) -> int:\n        m, n = len(mat), len(mat[0])\n        \n        #precipitate mat to histogram \n        for r in range(m):\n            for c in range(n):\n                if mat[r][c] and r > 0: \n                    mat[r][c] += mat[r-1][c] #histogram \n        \n        res = 0\n        for r in range(m):\n            stack = [] # mono-stack of indices of non-decreasing height for current row\n            dp = 0 # number of submatrices with all 1's ending at (r,c-1) so far\n            for c in range(n):\n                while stack and mat[r][stack[-1]] > mat[r][c]: \n                    start = stack.pop()                        #start\n                    end = stack[-1] if stack else -1           #end\n                    # difference in height between the taller bar and the current bar * width to bar before taller bar\n                    dp -= (mat[r][start] - mat[r][c])*(start - end) #adjust to reflect lower height\n\n                dp += mat[r][c] #count submatrices bottom-right at (i, j)\n                res += dp\n                stack.append(c)\n\n        return res", "class Solution:\n    def numSubmat(self, mat: List[List[int]]) -> int:\n        m, n = len(mat), len(mat[0])\n        dp = [[0] * n for _ in range(m)]\n        res = 0\n        for i in range(m):\n            dp[i][0] = 1 if mat[i][0] == 1 else 0\n            res += dp[i][0]\n            mini = dp[i][0]\n            for k in range(i-1, -1, -1):\n                mini = min(mini, dp[k][0])\n                res += mini\n                if mini == 0:\n                    break\n            \n            for j in range(1, n):\n                if mat[i][j] == 1:\n                    dp[i][j] = dp[i][j-1] + 1\n                    res += dp[i][j]\n                    \n                    mini = dp[i][j]\n                    for k in range(i-1, -1, -1):\n                        mini = min(mini, dp[k][j])\n                        res += mini\n                        if mini == 0:\n                            break\n        return res", "class Solution:\n    def numSubmat(self, mat: List[List[int]]) -> int:\n        if not mat: return 0\n        \n        rows, cols = len(mat), len(mat[0])\n        height = [0] * cols\n        output = 0\n        for r in range(rows):\n            for c in range(cols):\n                if mat[r][c] == 0:\n                    height[c] = 0\n                else:\n                    height[c] += 1\n                    v = height[c]\n                    for i in range(c, -1, -1):\n                        if height[i] == 0: break\n                        v = min(v, height[i])\n                        output += v\n        return output\n    \n    \n#     public int numSubmat(int[][] mat) {\n#         int m = mat.length, n = mat[0].length, height[] = new int[n], res = 0; \n#         for (int i = 0; i < m; i++) {\n#             for (int j = 0; j < n; j++) {\n#                 height[j] = mat[i][j] == 0 ? 0 : height[j] + 1;   //  height of histogram;\n#                 for (int k = j, min = height[j]; k >= 0 && min > 0; k--) {\n#                     min = Math.min(min, height[k]);\n#                     res += min;\n#                 }\n#             }\n#         }\n#         return res;\n#     }\n\n\n        \n        \n        1 + 1 + 2 + 1 + 1 + 3 + 2+ 2\n        \n        \n", "class Solution:\n    def numSubmat(self, mat: List[List[int]]) -> int:\n          \n        h, w = len(mat), len(mat[0])\n        \n        # dp table:\n        # record the maximum length of continuous 1 from left-most column to specified column\n        dp_acc_of_1 = [ [ 0 for _ in range(w)] for _ in range(h) ]\n        \n        for y in range(h):\n            for x in range(w):\n                \n                if x == 0:\n                    # left-most column\n                    dp_acc_of_1[y][x] = mat[y][x]\n                    \n                else:\n                    # not left-most column\n                    if mat[y][x] == 1:\n                        dp_acc_of_1[y][x] = dp_acc_of_1[y][x-1] + 1\n                        \n        \n        counter_of_rectangle = 0\n        \n        for y in range(h):\n            for x in range(w):\n                \n                # update the total number of rectangle, whose bottom right anchor point is [y][x]\n                \n                minimum_width = dp_acc_of_1[y][x]\n                \n                for h_idx in range(y, -1, -1):\n                    \n                    minimum_width = min(minimum_width, dp_acc_of_1[h_idx][x])\n                    counter_of_rectangle += minimum_width\n                    \n                    if minimum_width == 0:\n                        # no chance to make rectangle\n                        break\n                        \n        return counter_of_rectangle", "class Solution:\n    def numSubmat(self, mat: List[List[int]]) -> int:\n        acc, his = 0, [0] * len(mat[0])\n        for i, row in enumerate(mat):\n            for j, v in enumerate(row):\n                his[j] = his[j] + 1 if v else 0\n                cap = float('inf')\n                for height in his[:j + 1][::-1]:\n                    cap = min(cap, height)\n                    if not cap:\n                        break\n                    acc += cap\n                # print(i, j, acc)\n        return acc", "class Solution:\n    def numSubmat(self, mat: List[List[int]]) -> int:\n        h, w = len(mat), len(mat[0])\n        \n        # dp table:\n        # record the maximum length of continuous 1 from left-most column to specified column\n        dp_acc_of_1 = [ [ 0 for _ in range(w)] for _ in range(h) ]\n        \n        for y in range(h):\n            for x in range(w):\n                \n                if x == 0:\n                    # left-most column\n                    dp_acc_of_1[y][x] = mat[y][x]\n                    \n                else:\n                    # not left-most column\n                    if mat[y][x] == 1:\n                        dp_acc_of_1[y][x] = dp_acc_of_1[y][x-1] + 1\n                        \n        \n        counter_of_rectangle = 0\n        \n        for y in range(h):\n            for x in range(w):\n                \n                # update the total number of rectangle, whose bottom right anchor point is [y][x]\n                \n                minimum_width = dp_acc_of_1[y][x]\n                \n                for h_idx in range(y, -1, -1):\n                    \n                    minimum_width = min(minimum_width, dp_acc_of_1[h_idx][x])\n                    counter_of_rectangle += minimum_width\n                    \n                    if minimum_width == 0:\n                        # no chance to make rectangle\n                        break\n                        \n        return counter_of_rectangle", "class Solution:\n    def numSubmat(self, mat: List[List[int]]) -> int:\n        h, w = len(mat), len(mat[0])\n        dp_acc_of_1 = [ [ 0 for _ in range(w)] for _ in range(h) ]\n        for y in range(h):\n            for x in range(w):\n                if x == 0:\n                    dp_acc_of_1[y][x] = mat[y][x]\n                else:\n                    if mat[y][x] == 1:\n                        dp_acc_of_1[y][x] = dp_acc_of_1[y][x-1] + 1\n        counter_of_rectangle = 0\n        for y in range(h):\n            for x in range(w):               \n                minimum_width = dp_acc_of_1[y][x]\n                for h_idx in range(y, -1, -1):\n                    minimum_width = min(minimum_width, dp_acc_of_1[h_idx][x])\n                    counter_of_rectangle += minimum_width\n                    \n                    if minimum_width == 0:\n                        break\n        return counter_of_rectangle", "class Solution:\n    def numSubmat(self, mat: List[List[int]]) -> int:\n        row = len(mat)\n        col = len(mat[0])\n        \n        dp = [[0 for _ in range(col)] for _ in range(row)]\n        \n        # find the length of the left rec at point(i, j)\n        for i in range(row):\n            for j in range(col):\n                if mat[i][j]:\n                    dp[i][j] = dp[i][j-1] + 1 if j >= 1 else 1\n        \n        # from the right end (i,j) = (row_end, col_end) to find height = 1,2...\n        res = 0\n        for i in range(row):\n            for j in range(col):\n                leftnum = float(\\\"inf\\\")\n                for k in range(i, -1, -1):\n                    leftnum = min(leftnum, dp[k][j])\n                    \n                    if leftnum == 0:\n                        break\n                    res += leftnum\n                    \n        return res", "class Solution:\n    def numSubmat(self, mat: List[List[int]]) -> int:\n        if not mat:\n            return 0\n        m, n = len(mat), len(mat[0])\n        ret = 0\n        height = [0] * n\n        for i in range(m):\n            for j in range(n):\n                height[j] = 0 if not mat[i][j] else height[j] + 1\n                if mat[i][j]:\n                    h = height[j]\n                    for k in range(j, -1, -1):\n                        if mat[i][k]:\n                            h = min(h, height[k])\n                            ret += h\n                        else:\n                            break\n            # print(height)\n            # print(ret)\n        return ret\n", "class Solution:\n    def numSubmat(self, mat: List[List[int]]) -> int:\n        \n        h, w = len(mat), len(mat[0])\n        \n        # dp table:\n        # record the maximum length of continuous 1 from left-most column to specified column\n        dp_acc_of_1 = [ [ 0 for _ in range(w)] for _ in range(h) ]\n        \n        for y in range(h):\n            for x in range(w):\n                \n                if x == 0:\n                    # left-most column\n                    dp_acc_of_1[y][x] = mat[y][x]\n                    \n                else:\n                    # not left-most column\n                    if mat[y][x] == 1:\n                        dp_acc_of_1[y][x] = dp_acc_of_1[y][x-1] + 1\n                        \n        \n        counter_of_rectangle = 0\n        \n        for y in range(h):\n            for x in range(w):\n                \n                # update the total number of rectangle, whose bottom right anchor point is [y][x]\n                \n                minimum_width = dp_acc_of_1[y][x]\n                \n                for h_idx in range(y, -1, -1):\n                    \n                    minimum_width = min(minimum_width, dp_acc_of_1[h_idx][x])\n                    counter_of_rectangle += minimum_width\n                    \n                    if minimum_width == 0:\n                        # no chance to make rectangle\n                        break\n                        \n        return counter_of_rectangle\n", "# create integral sum with each row, reset at 0\n# 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.\n\nclass Solution:\n    def numSubmat(self, mat: List[List[int]]) -> int:\n        res = 0\n        m = mat\n        \n        for i in range(len(mat)):\n            for j in range(len(mat[0])):\n                if j > 0 and mat[i][j] == 1: #!j>0\n                    m[i][j] = m[i][j - 1] + 1\n        \n        for j in range(len(mat[0])):\n            for i in range(len(mat)):\n                mn = m[i][j]\n\n                for k in range(i, -1, -1): # from i to top  \n                    mn = min(mn, m[k][j])\n                    if mn == 0:\n                        break\n                    res += mn  #!\u6bcf\u770b\u5230\u4e00\u4e2a\u975e\u96f6\uff0c\u90fd\u8981\u52a0\n        return res\n                    \n        \n                \n", "class Solution:\n    def numSubmat(self, mat: List[List[int]]) -> int:\n        for i in range(1, len(mat)):\n            for j in range(len(mat[0])):\n                if mat[i][j]:\n                    mat[i][j] += mat[i-1][j]\n                \n        ans = 0\n        for i in range(len(mat)):\n            stack = []\n            cnt = 0\n            for j in range(len(mat[0])):\n                while stack and mat[i][stack[-1]]>mat[i][j]:\n                    last = stack.pop()\n                    prev = stack[-1] if stack else -1\n                    cnt -= (mat[i][last] - mat[i][j]) * (last - prev)\n                cnt += mat[i][j]\n                ans += cnt\n                stack.append(j)\n                \n            \n        return ans", "class Solution:\n    def numSubmat(self, mat: List[List[int]]) -> int:\n        m, n = len(mat), len(mat[0])\n        up = [[0]*n for _ in range(m)]\n        count = 0\n        for i in range(m):\n            for j in range(n):\n                if not mat[i][j]:\n                    continue\n                   \n                if i == 0:\n                    up[i][j] =  1\n                else:\n                    up[i][j] = up[i-1][j] + 1 \n                    \n                k = j \n                min_height = up[i][j]\n                while k >= 0 and mat[i][k]:\n                    min_height = min(min_height, up[i][k])\n                    count += min_height\n                    k -= 1 \n                    \n                \n        return count \n        \n        \n                \n            \n                \n                    \n        \n                \n                \n", "class Solution:\n    def numSubmat(self, mat: List[List[int]]) -> int:\n        # Make H matrix\n        H = mat \n        for i in range(1, len(mat)):\n            for j in range(len(mat[0])):\n                if H[i][j] == 0: continue\n                H[i][j] = H[i-1][j] + 1\n        \n        #count rect with bottom left corner i,j\n        total = 0\n        for i in range(len(H)):\n            for j in range(len(H[0])):\n                if H[i][j] == 0: continue\n                h = H[i][j]\n                total += h\n                for k in range(j+1, len(H[0])):\n                    if H[i][k] == 0: break\n                    h = min(H[i][k], h)\n                    total += h\n        return total\n", "class Solution:\n    def numSubmat(self, mat: List[List[int]]) -> int:\n        m = len(mat)\n        n = len(mat[0])\n        \n        heights = [0] * n\n        \n        count = 0\n        \n        for i in range(m):\n            for j in range(n):\n                if mat[i][j] == 0:\n                    heights[j] = 0\n                else:\n                    heights[j] += 1\n                   \n\n            for j in range(n):\n                k = j\n                smallest_height = heights[k]\n                \n                while k > -1 and heights[k] > 0:\n                    smallest_height = min(smallest_height, heights[k])\n                    count += smallest_height\n                    k -= 1\n\n        return count", "# O(mn*mn) time and O(1) space\nclass Solution:\n    def numSubmat(self, mat: List[List[int]]) -> int:\n        rows = len( mat )\n        cols = len( mat[0] )\n\n        \\\"\\\"\\\"\n        For each row, determine the number of submatrices of all 1's\n        that exist in that row. While moving horizontally along the\n        row, count the submatrices that terminate at each location.\n        Save the count of submatrices in the variable submatrices.\n        \\\"\\\"\\\"\n        submatrices = 0\n        for r in range( rows ):\n            submatrices += mat[r][0]\n            for c in range( 1, cols ):\n                if mat[r][c]:\n                    if c > 0:\n                        mat[r][c] = mat[r][c - 1] + 1\n                    submatrices += mat[r][c]\n\n        \\\"\\\"\\\"\n        At this point we have counted the submatrices that exist\n        within a single row. The code below counts the submatrices\n        that span multiple rows, then returns the sum of the two\n        counts.\n        \n        Process the above matrix one row at a time. Moving down each\n        column, determine the number of submatrices of all 1's that\n        start on that row looking left and span multiple rows.  Repeat\n        for each row and return the total number of submatrices.\n\n        For each 1 within a row, count the submatrices that contain\n        the 1, start on the same row either at or before the 1, and\n        span multiple rows. Proceed down the column that contains the 1\n        until reaching a 0 or the bottom row of the matrix. While\n        proceeding down a column, the width of the submatrices may\n        stay the same or gets thinner.\n        \\\"\\\"\\\"\n        for r in range( rows - 1 ):\n            for c in range( cols ):\n                if mat[r][c]:\n                    row = r + 1\n                    submatrix_width = mat[r][c]\n                    while row < rows and mat[row][c]:\n                        submatrix_width = min( submatrix_width, mat[row][c] )\n                        submatrices += submatrix_width\n                        row += 1\n        return submatrices", "class Solution:\n    def numSubmat(self, mat: List[List[int]]) -> int:\n        M=len(mat)\n        N=len(mat[0])\n        \n        mark=[[0 for _ in range(N)] for _ in range(M)]\n        \n        for m in range(M):\n            for n in range(N):\n                if n==0:\n                    mark[m][n]=mat[m][n]\n                else:\n                    mark[m][n]=mark[m][n-1]+1 if mat[m][n]==1 else 0\n        res=0          \n        for bottom in range(M):\n            for right in range(N):\n                Min=mark[bottom][right]\n                for upper in range(bottom+1)[::-1]:      \n                    Min=min(Min,mark[upper][right])\n                    if Min==0:\n                        break\n                    res+=Min\n                    \n        return res\n                    \n        \n#     ## Brute Force w/ Pruning O(N^2*M^2)\n#     def numSubmat(self, mat: List[List[int]]) -> int:\n#         M=len(mat)\n#         N=len(mat[0])\n#         res=0       \n        \n#         for top in range(M):\n#             for left in range(N):\n#                 bound=N ## to bound the right pointer\n#                 for bottom in range(top,M):                    \n#                     right=left\n#                     while right<bound:\n#                         if mat[bottom][right]==1:\n#                             res+=1\n#                             right+=1\n#                         else:\n#                             bound=right\n#                             break\n#         return res                  \n                        \n                        \n                    \n                \n", "class Solution:\n    def numSubmat(self, mat: List[List[int]]) -> int:\n        \n\n        rows = len( mat )\n        cols = len( mat[0] )\n\n\n        for r in range( rows ):\n            for c in range( 1, cols ):\n                if mat[r][c]:\n                    if c > 0:\n                        mat[r][c] = mat[r][c - 1] + 1\n\n\n        submatrices = 0\n        for r in range( rows ):\n            for c in range( cols ):\n                if mat[r][c]:\n                    row = r\n                    submatrix_width = mat[r][c]\n                    while row < rows and mat[row][c]:\n                        submatrix_width = min( submatrix_width, mat[row][c] )\n                        submatrices += submatrix_width\n                        row += 1\n        return submatrices\n", "class Solution:\n    def numSubmat(self, mat: List[List[int]]) -> int:\n        \n\n        rows = len( mat )\n        cols = len( mat[0] )\n\n\n        for r in range( rows ):\n            for c in range( 1, cols ):\n                if mat[r][c]:\n                    if c > 0:\n                        mat[r][c] = mat[r][c - 1] + 1\n\n        \n        submatrices = 0\n        for r in range( rows ):\n            for c in range( cols ):\n                if mat[r][c]:\n                    row = r\n                    submatrix_width = mat[r][c]\n                    while row < rows and mat[row][c]:\n                        submatrix_width = min( submatrix_width, mat[row][c] )\n                        submatrices += submatrix_width\n                        row += 1\n        return submatrices\n", "class Solution:\n    #TC: O(row*col*row)\n    #SC: O(row*col)\n    def numSubmat(self, mat: List[List[int]]) -> int:\n        nums = [[0]*len(mat[0]) for _ in range(len(mat))]\n        for row in range(len(mat)):\n            for col in range(len(mat[0])):\n                if col == 0:\n                    nums[row][col] = mat[row][col]\n                else:                \n                    if mat[row][col] == 0:\n                        nums[row][col] = 0\n                    else:\n                        nums[row][col] = nums[row][col-1] + 1 \n        res = 0        \n        for row in range(len(mat)):\n            for col in range(len(mat[0])):\n                Min = nums[row][col]\n                k = row\n                while(k>=0):\n                    if nums[k][col] == 0:\n                        break\n                    Min = min(nums[k][col], Min)\n                    res += Min\n                    k -= 1\n        return res", "class Solution:\n    def numSubmat(self, mat: List[List[int]]) -> int:\n        m, n = len(mat), len(mat[0])\n        for i in range(m):\n            for j in range(n):\n                if mat[i][j]:\n                    if j > 0:\n                        mat[i][j] = mat[i][j - 1] + 1\n        # for i in range(m):\n        #     for j in range(n):\n        #         if mat[i][j]:\n        #             if i > 0:\n        #                 mat[i][j] = mat[i - 1][j] + 1\n                    \n        total = 0\n        for i in range(m):\n            for j in range(n):\n                if mat[i][j]:\n                    row = i\n                    width = mat[i][j]\n                    while row < m and mat[row][j]:\n                        width = min(width, mat[row][j])\n                        total += width\n                        row += 1\n                        \n        return total", "class Solution:\n    \n    def numSubmat(self, mat: List[List[int]]) -> int:\n        nums = [[0]*len(mat[0]) for _ in range(len(mat))]\n        for row in range(len(mat)):\n            for col in range(len(mat[0])):\n                if col == 0:\n                    nums[row][col] = mat[row][col]\n                else:                \n                    if mat[row][col] == 0:\n                        nums[row][col] = 0\n                    else:\n                        nums[row][col] = nums[row][col-1] + 1 \n        res = 0        \n        for row in range(len(mat)):\n            for col in range(len(mat[0])):\n                Min = nums[row][col]\n                k = row\n                while(k>=0):\n                    if nums[k][col] == 0:\n                        break\n                    Min = min(nums[k][col], Min)\n                    res += Min\n                    k -= 1\n        return res\n", "class Solution:\n    def numSubmat(self, mat: List[List[int]]) -> int:\n        if len(mat) == 0:\n            return 0\n        hist = [0] * len(mat[0])\n        res = 0\n        for row in mat:\n            stack = []\n            count = 0\n            for i in range(len(row)):\n                if row[i]:\n                    hist[i] += row[i]\n                else:\n                    hist[i] = 0\n                \n                while stack and hist[stack[-1]] > hist[i]:\n                    jj = stack.pop()\n                    kk = stack[-1] if stack else -1\n                    count -= (hist[jj] - hist[i])*(jj - kk)\n                \n                count += hist[i]\n                res += count\n                stack.append(i)\n        \n        return res", "class Solution:\n    def numSubmat(self, mat: List[List[int]]) -> int:\n        n = len(mat)\n        m = len(mat[0])\n        count = 0\n        dp = [[0]*m for _ in range(n)]\n        for i in range(n):\n            c = 0\n            for j in range(m-1, -1, -1):\n                if mat[i][j]:\n                    c += 1\n                else:\n                    c = 0\n                dp[i][j] = c\n        # print(dp)\n        for j in range(m):\n            # print('j:',j)\n            for i in range(n):\n                if dp[i][j]:\n                    # print('i:',i)\n                    min_v = dp[i][j]\n                    count += dp[i][j]\n                    # print('count:', count)\n                    for k in range(i+1,n):\n                        # print('k:',k)\n                        min_v = min(min_v, dp[k][j])\n                        # print('min_v:',min_v)\n                        if not min_v: break\n                        count+= (k-i+1)*min_v - (k-i)*min_v\n                        # print('count:', count)\n                    # print()\n        return count\n                    \n                \n", "class Solution:\n    def numSubmat(self, mat: List[List[int]]) -> int:\n        for j in range(len(mat[0])):\n            for i in range(1, len(mat)):\n                if mat[i][j] != 0:\n                    if mat[i-1][j] != 0:\n                        mat[i][j] = mat[i-1][j] + 1\n        \n        cnt = 0\n        for i in range(0, len(mat)):\n            for j in range(len(mat[0])):\n                min_height = len(mat)\n                for k in range(j, -1, -1):\n                    if mat[i][k] == 0:\n                        break\n                    min_height = min(min_height, mat[i][k])\n                    cnt += min_height\n        \n        return cnt", "class Solution:\n    def numSubmat(self, mat: List[List[int]]) -> int:\n        \n        for i in range(len(mat)):\n            for j in range(1, len(mat[0])):\n                if mat[i][j]:\n                    mat[i][j] = mat[i][j - 1] + 1\n                    \n        # for row in mat:\n        #    print(row)\n        \n        count = 0\n        \n        for i in range(len(mat)):\n            for j in range(len(mat[0])):\n                if mat[i][j]:\n         #           print(i, j, mat[i][j])\n                    \n                    row = i\n                    width = mat[i][j]\n                    while row < len(mat) and mat[row][j]:\n                        width = min(width, mat[row][j])\n                        row += 1\n                        count += width\n        #                print(width)\n        return count", "class Solution:\n    def numSubmat(self, mat: List[List[int]]) -> int:\n        n = len(mat)\n        m = len(mat[0])\n        count = 0\n        for i in range(n):\n            c = 0\n            for j in range(m-1, -1, -1):\n                if mat[i][j]:\n                    c += 1\n                    mat[i][j] = c\n                else:\n                    c = 0\n                \n        for j in range(m):\n            for i in range(n):\n                if mat[i][j]:\n                    min_v = mat[i][j]\n                    count += mat[i][j]\n                    for k in range(i+1,n):\n                        if not mat[k][j]: break\n                        min_v = min(min_v, mat[k][j])\n                        count+= (k-i+1)*min_v - (k-i)*min_v\n        return count\n                    \n                \n", "class Solution:\n    def numSubmat(self, mat: List[List[int]]) -> int:\n        n = len(mat)\n        m = len(mat[0])\n        count = 0\n        dp = [[0]*m for _ in range(n)]\n        for i in range(n):\n            c = 0\n            for j in range(m-1, -1, -1):\n                if mat[i][j]:\n                    c += 1\n                else:\n                    c = 0\n                dp[i][j] = c\n        # print(dp)\n        for j in range(m):\n            # print('j:',j)\n            for i in range(n):\n                if dp[i][j]:\n                    # print('i:',i)\n                    min_v = dp[i][j]\n                    count += dp[i][j]\n                    # print('count:', count)\n                    for k in range(i+1,n):\n                        # print('k:',k)\n                        if not mat[k][j]: break\n                        min_v = min(min_v, dp[k][j])\n                        # print('min_v:',min_v)\n                        count+= (k-i+1)*min_v - (k-i)*min_v\n                        # print('count:', count)\n                    # print()\n        return count\n                    \n                \n", "class Solution:\n    def numSubmat(self, mat: List[List[int]]) -> int:\n        n = len(mat)\n        m = len(mat[0])\n        count = 0\n        # dp = [[0]*m for _ in range(n)]\n        for i in range(n):\n            c = 0\n            for j in range(m-1, -1, -1):\n                if mat[i][j]:\n                    c += 1\n                    mat[i][j] = c\n                else:\n                    c = 0\n                \n        # print(dp)\n        for j in range(m):\n            # print('j:',j)\n            for i in range(n):\n                if mat[i][j]:\n                    # print('i:',i)\n                    min_v = mat[i][j]\n                    count += mat[i][j]\n                    # print('count:', count)\n                    for k in range(i+1,n):\n                        # print('k:',k)\n                        if not mat[k][j]: break\n                        min_v = min(min_v, mat[k][j])\n                        # print('min_v:',min_v)\n                        count+= (k-i+1)*min_v - (k-i)*min_v\n                        # print('count:', count)\n                    # print()\n        return count\n                    \n                \n", "class Solution:\n    def numSubmat(self, mat: List[List[int]]) -> int:\n        \n#         rows = len( mat )\n#         cols = len( mat[0] )\n\n#         for r in range( rows ):\n#             for c in range( 1, cols ):\n#                 if mat[r][c]:\n#                     if c > 0:\n#                         mat[r][c] = mat[r][c - 1] + 1\n\n#         submatrices = 0\n#         for r in range( rows ):\n#             for c in range( cols ):\n#                 if mat[r][c]:\n#                     row = r\n#                     submatrix_width = mat[r][c]\n#                     while row < rows and mat[row][c]:\n#                         submatrix_width = min( submatrix_width, mat[row][c] )\n#                         submatrices += submatrix_width\n#                         row += 1\n#         return submatrices\n        \n        \n        res = 0\n        \n        for i in range(len(mat)):\n            for j in range(1, len(mat[0])):\n                if mat[i][j]:\n                    if j>0:\n                        mat[i][j] = mat[i][j-1] +1\n        \n        for i in range(len(mat)):\n            for j in range(len(mat[0])):\n                if mat[i][j]:\n                    r = i\n                    wid = mat[i][j]\n                    while r<len(mat) and mat[r][j]:\n                        wid = min(mat[r][j],wid)\n                        res += wid\n                        r +=1\n        return res", "class Solution:\n    def numSubmat(self, mat: List[List[int]]) -> int:\n        \n        \n        \n        # my solution ... 464 ms ... 70 % ... 15.5 MB ... 0 %\n        #  time: O(n*m*min(n,m))\n        # space: O(n*m)\n        \n        def func(i, j):\n            res = 0\n            height = float('inf')\n            for jj in range(j, -1, -1):\n                height = min(height, cnt[i][jj][1])\n                if not height:\n                    break\n                res += height  # \u3010(i,jj)\u4e3a\u5de6\u4e0b\u89d2\uff0c(i,j)\u4e3a\u53f3\u4e0b\u89d2\u3011\u7684\u77e9\u5f62\u4e2a\u6570\n            return res\n        \n        n, m = len(mat), len(mat[0])\n        cnt = [[0]*m for _ in range(n)]\n        tot = 0\n        for i in range(n):\n            for j in range(m):\n                if not mat[i][j]:\n                    cnt[i][j] = (0, 0)  # cnt[i][j] = (ij\u53ca\u5de6\u4fa71\u7684\u4e2a\u6570\uff0cij\u53ca\u4e0a\u65b91\u7684\u4e2a\u6570)\n                else:\n                    lft = cnt[i][j-1][0] + 1 if j > 0 else 1\n                    top = cnt[i-1][j][1] + 1 if i > 0 else 1\n                    cnt[i][j] = (lft, top)\n                    tot += func(i, j)\n        return tot\n        \n        \n", "class Solution:\n    def numSubmat(self, mat: List[List[int]]) -> int:\n        ## https://leetcode.com/problems/count-submatrices-with-all-ones/discuss/720265/Java-Detailed-Explanation-From-O(MNM)-to-O(MN)-by-using-Stack\n        ## similar idea: 84. Largest Rectangle in Histogram\n        ## process row by row\n        def helper(h): ## h is the effective cummulative height at position j\n            res = 0 \n            st = []\n            ## store number of rectangle (all ones) with h[i] as bottom-right corner\n            sum_ = [0] * len(h) \n            for i in range(len(h)):\n                ## pop those higher blocks, since it will not give more rectangles\n                while len(st)>0 and h[st[-1]]>=h[i]:\n                    st.pop()\n                \n                ## if we have a lower block in the stack\n                if len(st)>0:\n                    left_bound = st[-1]\n                    ## Extend the previous rectangular at index \\\"left_bound\\\". \n                    ## every rectangle that has left_bound as bottom-right corner can be extended to current index\n                    ## thus sum_[i] += sum_[left_bound] \n                    ## add rectangles that have height same as h[left_bound]\n                    sum_[i] += sum_[left_bound] \n                    sum_[i] += h[i] * (i-left_bound) ## add rectangles with height h[i] \n                                                     ## width =  (i - left_bound)\n                else:\n                    sum_[i] = h[i] * (i+1) # left_bound = -1 \n                \n                st.append(i)\n                \n            return sum(sum_)\n        \n        res = 0\n        h = [0] * len(mat[0])\n        for i in range(len(mat)):\n            for j in range(len(mat[0])):\n                if mat[i][j] == 1:\n                    h[j] += 1\n                else:\n                    h[j] = 0 \n                    \n            res += helper(h)\n        return res\n                \n        \n", "class Solution:\n    def numSubmat(self, mat: List[List[int]]) -> int:\n        n = len(mat)\n        m = len(mat[0])\n        # for x in mat: print(x) \n        count = 0\n        for i in range(n):\n            c = 0\n            for j in range(m-1, -1, -1):\n                if mat[i][j]:\n                    c += 1\n                    mat[i][j] = c\n                else:\n                    c = 0\n        \n        for j in range(m):\n            for i in range(n):\n                if mat[i][j]:\n                    min_v = mat[i][j]\n                    count += mat[i][j]\n                    for k in range(i+1,n):\n                        if not mat[k][j]: break\n                        min_v = min(min_v, mat[k][j])\n                        count+= (k-i+1)*min_v - (k-i)*min_v\n        return count\n                    \n                \n", "class Solution:\n    def numSubmat(self, g: List[List[int]]) -> int:\n        # traverse grid, if value is \\\"1\\\"\n        # record increasing \\\"width\\\" from left, or clear to zero on grid == 0\n        # across rows, submatrix count is:\n        # current width + min(curr width, prev width) + ...\n        # stepping down till grid boundary or g[r][c] zero value\n        # O(MN * N) time, O(1) space\n\n        rows, cols, res = len(g), len(g[0]), 0\n\n        for r in range(rows):\n            width = 0\n            for c in range(cols):\n                # increment row width from left\n                if g[r][c]:\n                    width += 1\n                    g[r][c] = width\n                else:\n                    width = 0\n\n                # account for current row submatrix count\n                res += width\n\n                # account for previous row submatrix count\n                row, prev_width = r, width\n                while row > 0 and g[row-1][c]:\n                    prev_width = min(prev_width, g[row-1][c])\n                    res = res + prev_width\n                    row -= 1\n\n        return res", "class Solution:\n    def numSubmat(self, mat: List[List[int]]) -> int:\n        row = len(mat)\n        col = len(mat[0])\n        \n        res = 0\n        dp = [[0 for _ in range(col)] for _ in range(row)]\n        \n        for i in range(row):\n            for j in range(col-1, -1, -1):\n                if mat[i][j] == 1:\n                    dp[i][j] = mat[i][j]\n                    if j < col-1:\n                        dp[i][j] += dp[i][j+1]\n        print(dp)                       \n        for i in range(row):\n            for j in range(col):\n                if mat[i][j] == 1:\n                    curr_row = i\n                    width = dp[curr_row][j]\n                    while curr_row < row and dp[curr_row][j] >= 1:\n                        width = min(dp[curr_row][j], width)\n                        res += width\n                        curr_row +=1\n        return res\n                        \n                                             \n", "class Solution:\n    def numSubmat(self, mat) -> int:\n        m, n = len(mat), len(mat[0])\n        self.count = 0\n        \n        for i in range(m):\n            for j in range(n):\n                if mat[i][j]:\n                    if j > 0:\n                        mat[i][j] += mat[i][j-1]\n        \n        for i in range(m):\n            for j in range(n):\n                if mat[i][j]:\n                    row = i \n                    submatrix_width = mat[i][j]\n                    while row < m and mat[row][j]:\n                        submatrix_width = min(submatrix_width, mat[row][j])\n                        self.count += submatrix_width\n                        row += 1\n        return self.count", "class Solution:\n    def numSubmat(self, mat: List[List[int]]) -> int:\n        \n        # for each row, calculate how many matrices can you build with all ones\n        \n        # then for each cell keep increasing height and taking minimum and adding its count\n        \n        if not mat:\n            return 0\n        \n        for row in range(len(mat)):\n            for col in range(len(mat[0])):\n                count = 0\n                if mat[row][col] == 1:\n                    for index in range(col,len(mat[0])):\n                        if mat[row][index]:\n                            count +=1\n                        else:\n                            break\n                            \n                mat[row][col] = count\n        \n        # now we take each cell and increase height one by one and keep adding to the\n        # final answer\n        ans = 0\n        for row in range(len(mat)):\n            for col in range(len(mat[0])):\n                count = 0\n                if mat[row][col]: # atleast some matrix starts at this point\n                    min_width = mat[row][col]\n                    for index in range(row,len(mat)):\n                        if not mat[index][col]: # can't expand matrix anymore\n                            break \n                        min_width = min(min_width, mat[index][col])\n                        count += min_width\n                ans += count\n                \n        return ans\n                    #keep increasing \n        \n        \n        \n        \n                \n", "class Solution:\n    def numSubmat(self, mat: List[List[int]]) -> int:\n        rows = len(mat);\n        cols = len(mat[0]);\n        dp = [[0 for _ in range(cols)] for _ in range(rows)];\n        for r in range(rows):\n            for c in range(cols):\n                if c == 0:\n                    dp[r][c] = mat[r][c];\n                else:\n                    if mat[r][c] == 1:\n                        dp[r][c] = dp[r][c-1] + 1;\n        count = 0;\n        for r in range(rows):\n            for c in range(cols):\n                min_width = dp[r][c];\n                for h_idx in range(r, -1, -1):\n                    min_width = min(min_width, dp[h_idx][c]);\n                    count += min_width\n                    if min_width == 0:\n                        break\n        return count", "class Solution:\n    def numSubmat(self, mat: List[List[int]]) -> int:\n        \n        dp = [[0 for _ in range(len(mat[0]))] for _ in range(len(mat))]\n        \n        for i in range(len(mat)):\n            for j in range(len(mat[0]) - 1, -1, -1):\n                if mat[i][j] == 1:\n                    dp[i][j] = 1 + (dp[i][j + 1] if j < len(mat[0]) - 1 else 0)\n        \n        ans = 0\n        for j in range(len(mat[0])):\n            for i in range(len(mat)):\n                t = float('inf')\n                \n                for k in range(i, len(mat)):\n                    t = min(t, dp[k][j])\n                    \n                    if t == 0:\n                        break\n                    else:\n                        ans += t\n        \n        return ans\n", "class Solution:\n    def numSubmat(self, mat: List[List[int]]) -> int:\n        m = len(mat)\n        if m == 0:\n            return 0\n        \n        n = len(mat[0])\n        if n == 0:\n            return 0\n        temp = [0, 0]\n        count = [[[0]*2 for l in range(n)] for _ in range(m)]\n        res = 0\n        for i in range(m):\n            for j in range(n):\n                if i == 0 and j == 0:\n                    res += mat[i][j]\n                    count[i][j][0] = mat[i][j]\n                    count[i][j][1] = mat[i][j]\n                    continue\n                elif i == 0 and mat[i][j]:\n                    count[i][j][1] += count[i][j-1][1]+1\n                    res += count[i][j][1]\n                    count[i][j][0] = mat[i][j]\n                elif j == 0 and mat[i][j]:\n                    count[i][j][0] += count[i-1][j][0]+1\n                    res += count[i][j][0]\n                    count[i][j][1] = mat[i][j]\n                elif mat[i][j]:\n                    res += 1\n                    count[i][j][1] += count[i][j-1][1]+1\n                    count[i][j][0] += count[i-1][j][0]+1\n                    if count[i][j-1][1]:\n                        res += count[i][j-1][1]\n                    if count[i-1][j][0]:\n                        res += count[i-1][j][0]\n                    findmin = count[i][j][0]\n                    for k in range(1, count[i][j][1]):\n                        findmin = min(findmin, count[i][j-k][0])\n                    # if count[i][j][0] > 1 and count[i][j][1] > 1 and count[i-1][j-1][0] >= 1:\n                    #     # count[i][j][2] = \n                    #     # res += min(count[i][j][0], count[i][j][1])-1\n                        res += findmin-1\n                    \n                # print(i, j, res)\n        # print(count)\n        return res", "from functools import lru_cache\nfrom itertools import product\n\n\nclass Solution:\n    def numSubmat(self, mat: List[List[int]]) -> int:\n        R, C = len(mat), len(mat[0])\n\n        @lru_cache(None)\n        def leftsum(i, j):\n            if j < 0 or mat[i][j] == 0:\n                return 0\n            return 1 + leftsum(i, j - 1)\n        \n        ret = 0\n        \n        for bottom, j in product(list(range(R)), list(range(C))):\n            width = j + 1\n            for top in range(bottom, -1, -1):\n                width = min(leftsum(top, j), width)\n                if width == 0:\n                    break\n                ret += width\n\n        return ret\n", "class Solution:\n    def numSubmat(self, mat: List[List[int]]) -> int:\n        if not mat:\n            return 0\n    \n        for i in range(len(mat)):\n            for j in range(1, len(mat[0])):\n                mat[i][j] = 1 + mat[i][j-1] if mat[i][j] !=0 else 0\n\n        for j in range(len(mat[0])):\n            # keep a mono increasing stack\n            # if current num >= prv num-> curr num + prev mat[i-1][j]\n            # if current num < prv num -> clean stack\n\n            stack = [(-1, -1)] # index, value\n            for i in range(len(mat)):\n                while stack and mat[i][j] < stack[-1][1]:\n                    stack.pop()\n                stack.append((i, mat[i][j]))\n                mat[i][j] = mat[i][j] * (i - stack[-2][0]) + (mat[stack[-2][0]][j] if stack[-2][0] != -1 else 0)\n\n        return sum([sum(arr) for arr in mat])", "class Solution:\n    def numSubmat(self, mat: List[List[int]]) -> int:\n        count = 0\n        r = len(mat)\n        c = len(mat[0])\n        for i in range(r):\n            for j in range(c-2, -1, -1):\n                if mat[i][j] == 1:\n                    mat[i][j] += mat[i][j+1]\n        for i in range(r):\n            for j in range(c):\n                minm = mat[i][j]\n                d = i\n                while d < r and mat[d][j] != 0:\n                    minm = min(minm, mat[d][j])\n                    count += minm\n                    d += 1\n        return count", "class Solution:\n    def numSubmat(self, mat: List[List[int]]) -> int:\n        m = len(mat)\n        if m == 0: return 0\n        n = len(mat[0])\n        if n == 0: return 0\n        dp = [[0] * n for _ in range(m)]\n        for i in range(m):\n            for j in range(n):\n                if j == 0:\n                    dp[i][j] = mat[i][j]\n                else:\n                    if mat[i][j] == 1:\n                        dp[i][j] = dp[i][j-1] + 1\n        result = 0\n        for i in range(m):\n            for j in range(n):\n                min_width = dp[i][j]\n                for row_idx in range(i,-1,-1):\n                    min_width = min(min_width, dp[row_idx][j])\n                    result += min_width\n                    if min_width == 0:\n                        break\n        return result\n", "class Solution:\n    def numSubmat(self, mat: List[List[int]]) -> int:\n        if not mat: \n            return 0\n        rows = len(mat)\n        cols = len(mat[0])\n        n = 0\n        \n        for top in range(rows):\n            for left in range(cols):\n                bottom = rows\n                for right in range(left, cols):\n                    scan = top\n                    while scan < bottom and mat[scan][right]: scan += 1\n                    bottom = scan\n                    n += bottom - top\n                    if bottom == top: break\n        return n", "class Solution:\n    def numSubmat(self, mat: List[List[int]]) -> int:\n        if not mat: return 0\n        rows = len(mat)\n        cols = len(mat[0])\n        n = 0\n        for top in range(rows):\n            for left in range(cols):\n                bottom = rows\n                for right in range(left, cols):\n                    scan = top\n                    while scan < bottom and mat[scan][right]: scan += 1\n                    bottom = scan\n                    n += bottom - top\n                    if bottom == top: break\n        return n\n", "class Solution:\n    def numSubmat(self, mat: List[List[int]]) -> int:\n        n = len(mat)\n        m = len(mat[0])\n        width = [[0 for _ in range(m)] for _ in range(n)]\n        for i in range(n):\n            width[i][0] = mat[i][0]\n        for i in range(n):\n            for j in range(1,m):\n                if(mat[i][j]!=0):\n                    width[i][j] = width[i][j-1]+1\n        \n        \n        ans = 0\n        for i in range(n):\n            for j in range(m):\n                if(mat[i][j] != 0):\n                    min_width = width[i][j]                    \n                    for new_i in range(i,-1,-1):\n                        if(mat[new_i][j] == 0):\n                            break\n                        min_width = min(min_width, width[new_i][j])\n                        ans += min_width\n        return ans\n                        \n                        \n                \n        \n", "class Solution:\n    def numSubmat(self, mat: List[List[int]]) -> int:\n        m, n = len(mat), len(mat[0])\n        for i in range(1, m):\n            for j in range(n):\n                if mat[i][j]:\n                    mat[i][j] += mat[i - 1][j]\n        result = 0\n        for i in range(m):\n            for k in range(i, m):\n                height = k - i + 1\n                width = 0\n                for j in range(n):\n                    if mat[k][j] >= height:\n                        width += 1\n                        result += width\n                    else:\n                        width = 0\n        return result", "def no_of_submat(r, c):\n    return r*c\n    \n    \nclass Solution:\n    def numSubmat(self, mat: List[List[int]]) -> int:\n        n = len(mat)\n        m = len(mat[0])\n        count = 0\n        dp = [[0]*m for _ in range(n)]\n        for i in range(n):\n            c = 0\n            for j in range(m-1, -1, -1):\n                if mat[i][j]:\n                    c += 1\n                else:\n                    c = 0\n                dp[i][j] = c\n        # print(dp)\n        for j in range(m):\n            # print('j:',j)\n            for i in range(n):\n                if dp[i][j]:\n                    # print('i:',i)\n                    min_v = dp[i][j]\n                    count += no_of_submat(1,dp[i][j])\n                    # print('count:', count)\n                    for k in range(i+1,n):\n                        # print('k:',k)\n                        min_v = min(min_v, dp[k][j])\n                        # print('min_v:',min_v)\n                        if not min_v: break\n                        count+= no_of_submat(k-i+1, min_v)-no_of_submat(k-i, min_v)\n                        # print('count:', count)\n                    # print()\n        return count\n                    \n                \n", "class Solution:\n    def numSubmat(self, mat: List[List[int]]) -> int:\n        if not mat: return 0\n        \n        m, n = len(mat), len(mat[0])\n        \n        count = 0\n        for i in range(m):\n            for j in range(n):\n                if mat[i][j] == 1:\n                    count += 1\n                    up, left = i - 1, j - 1\n                    \n                    while up >= 0 and mat[up][j] == 1: up -= 1\n                    count += i - up - 1\n                    \n                    while left >= 0 and mat[i][left] == 1: left -= 1\n                    count += j - left - 1\n                    \n                    k = i - 1\n                    while k > up:\n                        l = j - 1\n                        if mat[k][l] == 0: break\n                        while l > left:\n                            if mat[k][l] == 1: \n                                count += 1\n                                l -= 1\n                            else: \n                                left = l\n                                break\n                        k -= 1\n        return count", "class Solution:\n    def numSubmat(self, mat: List[List[int]]) -> int:\n        for i in range(len(mat)):\n            for j in range(len(mat[0])):\n                if not mat[i][j]:\n                    continue\n                mat[i][j] += mat[i-1][j] if i-1 >= 0 else 0\n        # count submatrices with all 1s with bottom right corner at (i,j)\n        ret = 0\n        for i in range(len(mat)):\n            row = mat[i]\n            stack = []\n            tot = 0\n            for j in range(len(row)):\n                ths = 1\n                while stack and stack[-1][0] >= row[j]:\n                    popped = stack.pop()\n                    tot -= popped[0] * popped[1]\n                    ths += popped[1]\n                stack.append([row[j], ths])\n                tot += ths * row[j]\n                ret += tot\n        return ret", "class Solution:\n    def numSubmat(self, mat: List[List[int]]) -> int:\n        dph = [[0 for j in range(len(mat[0])+1)] for i in range(len(mat)+1)]\n        dpv = [[0 for j in range(len(mat[0])+1)] for i in range(len(mat)+1)]\n        dps = [[[] for j in range(len(mat[0])+1)] for i in range(len(mat)+1)]\n        \n        counts = 0\n        for i in range(1,len(mat)+1):\n            for j in range(1,len(mat[0])+1):\n                if mat[i-1][j-1]==1:\n                    dpv[i][j] = dpv[i-1][j]+1\n                    dph[i][j] = dph[i][j-1]+1\n                    \n                    if dpv[i][j]-1>dpv[i-1][j-1]:\n                        tmp = collections.deque([dph[i][j]])\n                        for k in range(dpv[i][j]-1):\n                            if k<dpv[i-1][j-1]:\n                                tmp.append(min(dps[i-1][j-1][k]+1,dph[i][j]))\n                            else:\n                                tmp.append(1)\n                    else:\n                        tmp = collections.deque([dph[i][j]])\n                        for k in range(dpv[i][j]-1):\n                            tmp.append(min(dps[i-1][j-1][k]+1,dph[i][j]))\n                    dps[i][j] = tmp\n                    counts += sum(tmp)\n                    \n                    \n        print(dps)\n        return counts", "class Solution:\n    def numSubmat(self, mat: List[List[int]]) -> int:\n        m = len(mat)\n        n = len(mat[0])\n        dp = [[mat[i][j] for j in range(n)] for i in range(m)]\n        for i in range(m):\n            for j in range(n-2, -1, -1):\n                if mat[i][j] == 1:\n                    dp[i][j] = dp[i][j+1] + 1\n        # for row in dp:\n        #     print(row)\n        res = 0\n        for i in range(m):\n            for j in range(n):\n                k = i\n                mn = dp[i][j]\n                while k < m and dp[k][j] != 0:\n                    mn = min(mn, dp[k][j])\n                    res += mn\n                    k += 1\n        return res", "class Solution:\n#     def numSubmat(self, mat: List[List[int]]) -> int:\n#         result = 0\n#         for i in range(len(mat)):\n#             for j in range(len(mat[i])):\n#                 if mat[i][j] == 1:\n#                     prev_row_width = -1\n#                     for row in range(i, len(mat)):\n#                         for col in range(j, len(mat[i])):\n#                             if mat[row][col] == 1 and (prev_row_width == -1 or col - j + 1 <= prev_row_width):\n#                                 result += 1\n#                                 # print(\\\"Prev Width:\\\", prev_row_width)\n#                                 # print(\\\"Current Width:\\\", col - j + 1)\n#                                 # print(\\\"Rectangle with coordinates ({}, {}) and ({}, {})\\\".format(i, j, row, col))\n#                             else:\n#                                 prev_row_width = col - j\n#                                 break\n                                    \n                        \n#         return result\n\n#     def numSubmat(self, mat: List[List[int]]) -> int:\n#         result = 0\n#         n = len(mat)\n#         m = len(mat[0])\n#         consecutive_ones = [[0] * m for _ in range(n)]\n        \n#         for i in range(n):\n#             curr_ones = 0\n#             for j in range(m - 1, -1, -1):\n#                 if mat[i][j] == 1:\n#                     curr_ones += 1\n#                 else:\n#                     curr_ones = 0\n#                 consecutive_ones[i][j] = curr_ones\n        \n#         # print(consecutive_ones)\n        \n#         for i in range(n):\n#             for j in range(m):\n#                 if mat[i][j] == 1:\n#                     prev_row_width = float('inf')\n#                     for row in range(i, n):\n#                         curr_width = consecutive_ones[row][j]\n#                         # print(\\\"Prev Width:\\\", prev_row_width)\n#                         # print(\\\"Current Width:\\\",curr_width)\n\n#                         if curr_width == 0:\n#                             break\n                        \n#                         # print(\\\"Rectangle with coordinates ({}, {}) and ({}, {})\\\".format(i, j, row, j + curr_width - 1))\n#                         result += min(prev_row_width, curr_width)\n#                         prev_row_width = min(prev_row_width, curr_width)\n                        \n#         return result\n\n    def numSubmat(self, mat: List[List[int]]) -> int:\n        result = 0\n        n = len(mat)\n        m = len(mat[0])\n        consecutive_ones = [[0]*m for _ in range(n)]\n        overall_ones = []\n        \n        for i in range(n):\n            c = 0\n            for j in range(m - 1, -1, -1):\n                if mat[i][j] == 1:\n                    c += 1\n                    overall_ones.append((i, j))\n                else:\n                    c = 0\n                consecutive_ones[i][j] = c\n                \n        while len(overall_ones) != 0:\n            leftmost_point = overall_ones.pop()\n            i = leftmost_point[0]\n            j = leftmost_point[1]\n            \n            prev_row_width = float('inf')\n            for row in range(i, n):\n                curr_width = consecutive_ones[row][j]\n                \n                if curr_width == 0:\n                    break\n                \n                result += min(prev_row_width, curr_width)\n                prev_row_width = min(prev_row_width, curr_width)\n        \n                    \n        return result\n                \n                \n        \n        \n        \n", "class Solution:\n    def numSubmat(self, mat: List[List[int]]) -> int:\n        rows = len(mat)\n        cols = len(mat[0])\n        submatrices = 0\n        for r in range(rows):\n            submatrices += mat[r][0]\n            for c in range(1,cols):\n                if mat[r][c] != 0:\n                    if c > 0:\n                        mat[r][c] = mat[r][c - 1] + 1\n                    submatrices += mat[r][c]\n            \n                    \n               \n        for r in range(rows - 1):\n            for c in range(cols):\n                if mat[r][c] != 0:\n                    row = r + 1\n                    submatrix_width = mat[r][c]\n                    while row < rows and mat[row][c] != 0:\n                        submatrix_width = min(submatrix_width,mat[row][c])\n                        \n                        submatrices += submatrix_width\n                        row += 1\n        return submatrices", "class Solution:\n    def numSubmat(self, mat: List[List[int]]) -> int:\n        m = len(mat)\n        n = len(mat[0])\n\n        for i in range(m):\n            for j in reversed(range(n-1)):\n                if mat[i][j] == 1:\n                    mat[i][j] = mat[i][j+1] + 1               \n\n        def countSubmat(i, j):\n            top = i\n            left = j\n            bound = n\n            counter = 0\n            while i < m and mat[i][j] > 0:\n                counter += min(bound, mat[i][j])\n                bound = min(bound, mat[i][j])\n                i += 1\n            return counter\n        \n        total = 0\n        for i in range(m):\n            for j in range(n):\n                if mat[i][j] > 0:\n                    total += countSubmat(i, j)\n        \n        return total", "class Solution:\n    def get_matrix_cnt(self, cur_row_height):\n        res = 0\n        for i, polm in enumerate(cur_row_height):\n            \n            if polm > 0:\n                for cur_height in range(1, polm+1):\n                    res += 1\n                    cur_index = i+1\n                    while cur_index < len(cur_row_height) and cur_row_height[cur_index] >= cur_height:\n                        res +=1\n                        cur_index += 1\n        return res\n                    \n        \n    def numSubmat(self, mat: List[List[int]]) -> int:\n        \n        m = len(mat)\n        n = len(mat[0])\n        \n        cur_row_height = [0] * n\n        total = 0\n        for row in range(m):\n            # get cumulated height based on current row\n            for col in range(n):\n                if mat[row][col] == 0:\n                    cur_row_height[col] = 0\n                else:\n                    cur_row_height[col] += 1\n            \n            #print(cur_row_height)\n            cur_cnt = self.get_matrix_cnt(cur_row_height)\n            total += cur_cnt\n            #print(cur_cnt)\n        return total", "class Solution:\n    def numSubmat(self, mat: List[List[int]]) -> int:\n        M, N = len(mat), len(mat[0])\n\n        def count_submatrices(a, b):\n            count, bound = 0, N\n\n            for i in range(a, M):\n                y = b\n                while y < bound:\n                    if mat[i][y]:\n                        count += 1\n                    else:\n                        bound = y\n                    y += 1\n\n                # bound is the boundary of col, if mat[a][b] == 0, means top-left cornor is 0, we won't have any\n                # submatrics with all 1's, so return directly\n                if bound == b:\n                    return count\n            return count\n\n        count = 0\n        for i in range(M):\n            for j in range(N):\n                count += count_submatrices(i, j)\n        return count\n\n\n", "class Solution:\n    def numSubmat(self, mat: List[List[int]]) -> int:\n        res, lr, lc = 0, len(mat), len(mat[0]) if mat else 0\n        for i in range(lr):\n            for j in range(lc):\n                if mat[i][j]:\n                    cur, x, limit = 0, i, lc\n                    while x < lr:\n                        y = j\n                        if not mat[x][y]:\n                            break\n                        while y < limit:\n                            if not mat[x][y]:\n                                limit = y\n                                break\n                            cur, y = cur + 1, y + 1\n                        x += 1\n                    res += cur\n        return res\n", "class Solution:\n    def numSubmat(self, mat: List[List[int]]) -> int:\n        m = len(mat)\n        if m == 0: return 0\n        n = len(mat[0])\n        if n == 0: return 0\n        \n        a = [None for _ in range(m)]\n        for i in range(m):\n            a[i] = []\n            for j in range(n):\n                a[i].append([0, 0])\n        \n        for i in range(m):\n            for j in range(n-1, -1, -1):\n                if i == n-1:\n                    a[i][j][0] = 1 if mat[i][j] == 1 else 0\n                else:\n                    a[i][j][0] = 1 + a[i-1][j][0] if mat[i][j] == 1 else 0\n        \n        for j in range(n):\n            for i in range(m):\n                if i == 0:\n                    a[i][j][1] = 1 if mat[i][j] == 1 else 0\n                else:\n                    a[i][j][1] = 1 + a[i-1][j][1] if mat[i][j] == 1 else 0\n        \n        ans = 0\n        for i in range(m):\n            j = 0\n            while j < n:\n                if mat[i][j] == 0:\n                    j += 1\n                else:\n                    minH = a[i][j][1]\n                    k = j\n                    while k < n and mat[i][k] == 1:\n                        minH = min(minH, a[i][k][1])\n                        ans += minH\n                        k += 1\n                    j += 1\n        return ans\n                    \n", "class Solution:\n    def numSubmat(self, mat: List[List[int]]) -> int:\n        n = len(mat)\n        m = len(mat[0])\n        res = 0\n        for i in  range(n):\n            for j in range(m):\n                if mat[i][j]:\n                    if j: mat[i][j] += mat[i][j-1]\n                    width = mat[i][j]\n                    k=i\n                    while k>=0 and mat[k][j]>0: \n                        width = min(width, mat[k][j])\n                        res += width\n                        k -= 1\n                    \n        return res"]