Count Submatrices With All Ones

Problem Description

Given an m x n binary matrix mat, return the number of submatrices that have all ones.

Key Insights

• A submatrix is defined by its top-left and bottom-right corners.
• We can use dynamic programming to keep track of the height of consecutive 1s for each column.
• For each cell, we can determine how many rectangles can be formed using that cell as the bottom-right corner by leveraging the previously calculated heights.

Space and Time Complexity

Time Complexity: O(m * n) Space Complexity: O(n)

Solution

To solve the problem, we use a dynamic programming approach. We maintain an array height that stores the height of consecutive 1s in each column for every row. For each cell in the matrix, we calculate the number of submatrices that can end at that cell by iterating through the heights. The main steps are:

1. Initialize a height array to keep track of the heights of 1s for each column.
2. Iterate through each cell in the matrix, updating the height array.
3. For each cell, calculate the number of possible rectangles that can be formed using the height of 1s.

Code Solutions