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.Problem Overview: Given a binary matrix, count how many submatrices contain only 1s. Every possible rectangle inside the matrix must be checked, but doing that naively is too slow. The key observation: each row can be treated like the base of a histogram representing consecutive vertical ones.
Approach 1: Dynamic Programming with Upward Expansion (O(m * n^2) time, O(n) space)
Build a DP array where dp[r][c] represents the number of consecutive 1s ending at (r, c) horizontally. For each cell containing 1, treat it as the bottom-right corner of potential submatrices. Move upward row by row while maintaining the minimum width of consecutive ones seen so far. Add this width to the answer at every step because it represents how many valid submatrices end at that row. The approach uses ideas from dynamic programming and works well for moderate matrix sizes.
Approach 2: Histogram + Monotonic Stack (O(m * n) time, O(n) space)
Convert each row into a histogram where height[c] counts consecutive vertical ones up to that row. The problem becomes counting how many submatrices end at the current row using this histogram. Use a monotonic stack to efficiently calculate the number of rectangles contributed by each column while maintaining increasing heights. When a smaller height appears, pop taller bars and adjust the count of rectangles they contributed. This avoids rechecking previous columns and ensures each element is pushed and popped at most once.
The histogram view transforms the 2D problem into repeated 1D rectangle counting. Combined with stack-based range aggregation, it reduces redundant computations across columns. This pattern commonly appears in matrix problems where vertical accumulation converts 2D constraints into histogram problems.
Recommended for interviews: The histogram + monotonic stack solution is the expected optimal answer with O(m * n) time. The DP approach is easier to derive and shows understanding of submatrix expansion, but the stack-based histogram technique demonstrates stronger algorithmic depth and familiarity with advanced array processing patterns.
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.
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.
C++
JavaScript
Time Complexity: O(m * n^2), Space Complexity: O(m*n).
We can enumerate the bottom-right corner (i, j) of the matrix, and then enumerate the first row k upwards. The width of the matrix with (i, j) as the bottom-right corner in each row is min_{k leq i} g[k][j], where g[k][j] represents the width of the matrix with (k, j) as the bottom-right corner in the k-th row.
Therefore, we can preprocess a 2D array g[i][j], where g[i][j] represents the number of consecutive 1s from the j-th column to the left in the i-th row.
The time complexity is O(m^2 times n), and the space complexity is O(m times n). Here, m and n are the number of rows and columns of the matrix, respectively.
Python
Java
C++
Go
TypeScript
Rust
JavaScript
| 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). |
| Enumeration + Prefix Sum | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Dynamic Programming with Upward Expansion | O(m * n^2) | O(n) | Good first solution in interviews. Easy to reason about using width tracking. |
| Histogram + Monotonic Stack | O(m * n) | O(n) | Optimal solution. Best for large matrices and expected in strong interview answers. |
Leetcode 1504. Count Submatrices With All Ones • Fraz • 34,865 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