LeetCode Solutions Blog

Count Submatrices With All Ones

Number: 1628

Difficulty: Medium

Paid? No

Companies: Google

Problem Description

Given a binary matrix, count the number of submatrices that contain all ones. A submatrix is any contiguous block of cells within the matrix, and the goal is to count every submatrix where every element is 1.

Key Insights

Use dynamic programming to build a histogram of consecutive ones for each row.
For each row, treat the histogram as a base and count submatrices ending at that row.
Utilize a monotonic stack to efficiently compute the number of valid submatrices based on the histogram heights.
The key trick is to update the count by considering the minimum height as you extend submatrices to the left.

Space and Time Complexity

Time Complexity: O(m * n) where m is the number of rows and n is the number of columns. Space Complexity: O(n) for the histogram and stack.

Solution

The solution iterates row by row, building a histogram (array of heights) where each entry records the number of consecutive 1's ending at the current row. For each row, the problem of counting submatrices reduces to finding all sub-rectangles in a histogram. A monotonic stack helps to efficiently process each column in the histogram. For each column, while the current height is less than or equal to the top of the stack, we pop from the stack and update the count accordingly; this ensures that we only count submatrices that can extend to the current cell. Finally, the sum of the counts across rows gives the solution.

Code Solutions

# Python solution with line-by-line comments
def numSubmat(mat):
    # Get dimensions of the matrix.
    m, n = len(mat), len(mat[0])
    result = 0
    # Initialize histogram heights for each column.
    heights = [0] * n
    # Iterate through each row in the matrix.
    for r in range(m):
        # Update the histogram heights based on current row values.
        for c in range(n):
            if mat[r][c] == 1:
                heights[c] += 1  # Increase height if cell is 1.
            else:
                heights[c] = 0   # Reset height if cell is 0.
        # Use a monotonic stack to count submatrices ending at current row.
        stack = []
        cur_count = 0  # Count of submatrices ending at this row.
        # Process each column in the histogram.
        for c in range(n):
            count = 1  # At least one new rectangle ending at (r,c).
            # Maintain stack in increasing order of heights.
            while stack and stack[-1][0] >= heights[c]:
                h, cnt = stack.pop()
                # Subtract the excess count contributed by h over heights[c].
                count += cnt
                cur_count -= (h - heights[c]) * cnt
            cur_count += heights[c] * count
            stack.append((heights[c], count))
            # Add to the final result the count for submatrices ending at column c.
            result += cur_count
    return result

# Example usage:
if __name__ == "__main__":
    matrix = [[1,0,1],[1,1,0],[1,1,0]]
    print(numSubmat(matrix))  # Output should be 13