Problem statement

https://binarysearch.com/problems/Count-Rectangular-Submatrices/

Solution

Equal to Leetcode 1504. Count Submatrices With All Ones.

Complexity

It is O(mn) for time and space.

Code

class Solution:
    def solve(self, M):
        m, n, res = len(M), len(M[0]), 0
        H = [0]*(n + 1)
        for i in range(m):
            stack, dp = [-1], [0]*(n+1)
            for j in range(n):
                H[j] = M[i][j] * (H[j] + 1)
                while H[j] < H[stack[-1]]: stack.pop()
                dp[j] = dp[stack[-1]] + H[j]*(j - stack[-1])
                stack += [j]
            res += sum(dp)
        return res