Editorial

Solution walkthrough

Review the explanation, then compare the reference implementation.

Video explanation

Solution

Intuition

For a fixed bottom row, column heights count consecutive ones ending there. A rectangle ending at column j can choose any height up to the minimum across its column span. A monotonic stack groups spans whose limiting height is the current column, avoiding a scan of every possible left boundary.

Approach

Update each histogram height, resetting it at a zero. Pop stack indices whose heights are at least the current height, leaving the nearest strictly shorter column prev. If it exists, set count[j] = count[prev] + height[j] * (j - prev): earlier spans retain their previous minima, while newer starting positions are limited by the current height. With no shorter column, use height[j] * (j + 1). Push j and add its count to the answer. Summing over bottom rows and right boundaries counts every all-ones rectangle once.

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

        for i in range(n):
            stack = []
            count = [0] * m

            for j in range(m):
                if mat[i][j] == 0:
                    height[j] = 0
                else:
                    height[j] += 1
                while stack and height[stack[-1]] >= height[j]:
                    stack.pop()
                if stack:
                    prev = stack[-1]
                    count[j] = count[prev] + height[j] * (j - prev)
                else:
                    count[j] = height[j] * (j + 1)
                stack.append(j)
                res += count[j]

        return res

Complexity analysis

For an R × C matrix, every column index is pushed and popped at most once per row. The histogram/monotonic-stack algorithm therefore uses O(RC) time and O(C) auxiliary space.