Problem statement

https://leetcode.com/problems/count-submatrices-with-all-ones/

Solution

This problem is similar to Leetcode 0085. Maximal Rectangle, but now we need to find not the biggest rectangle, but number of rectangles. We still can use the idea of monotonic deque here.

Complexity

It is O(mn) for time and space.

Code

class Solution:
    def numSubmat(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

Remark

There is easier O(mn*min(m,n)) time complexity solution, using dp.