Given an m x n binary matrix mat, return the number of submatrices that have all ones.
Example 1:
Input: mat = [[1,0,1],[1,1,0],[1,1,0]] Output: 13 Explanation: There are 6 rectangles of side 1x1. There are 2 rectangles of side 1x2. There are 3 rectangles of side 2x1. There is 1 rectangle of side 2x2. There is 1 rectangle of side 3x1. Total number of rectangles = 6 + 2 + 3 + 1 + 1 = 13.
Example 2:
Input: mat = [[0,1,1,0],[0,1,1,1],[1,1,1,0]] Output: 24 Explanation: There are 8 rectangles of side 1x1. There are 5 rectangles of side 1x2. There are 2 rectangles of side 1x3. There are 4 rectangles of side 2x1. There are 2 rectangles of side 2x2. There are 2 rectangles of side 3x1. There is 1 rectangle of side 3x2. Total number of rectangles = 8 + 5 + 2 + 4 + 2 + 2 + 1 = 24.
Constraints:
1 <= m, n <= 150mat[i][j] is either 0 or 1.This approach converts each row of the matrix into a histogram by counting the number of continuous '1's above each cell, including the current cell. We then calculate the number of submatrices ending at each position using a monotonic stack to manage heights in order to calculate the width of possible rectangles.
This solution iterates over each possible row and calculates heights of histograms ending at each row. It uses a stack to efficiently count submatrices.
Java
Time Complexity: O(m * n^2), where m is the number of rows and n is the number of columns. Space Complexity: O(n) for the height and stack arrays.
Utilize dynamic programming to store the count of submatrices ending at each position (i, j). This solution leverages cumulative sums to efficiently count submatrices.
This C++ solution uses a 2D dynamic programming table to count the number of possible submatrices that can end at each cell and then iteratively reduces the potential width as we move up in rows to count valid submatrices.
JavaScript
Time Complexity: O(m * n^2), Space Complexity: O(m*n).
| Approach | Complexity |
|---|---|
| Histogram Approach | Time Complexity: O(m * n^2), where m is the number of rows and n is the number of columns. Space Complexity: O(n) for the height and stack arrays. |
| Dynamic Programming Approach | Time Complexity: O(m * n^2), Space Complexity: O(m*n). |
DP 56. Count Square Submatrices with All Ones | DP on Rectangles 🔥 • take U forward • 117,457 views views
Watch 9 more video solutions →Practice Count Submatrices With All Ones with our built-in code editor and test cases.
Practice on FleetCode