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.To solve #1504 Count Submatrices With All Ones, the key idea is to treat each row as the base of a histogram. For every cell, compute the number of consecutive 1s vertically above it using a dynamic programming array. This converts the matrix problem into a series of histogram problems.
Once the height of consecutive ones for each column is known, we determine how many submatrices end at the current row. A monotonic stack can be used to efficiently count valid subarrays of heights, ensuring that each column contributes to the number of submatrices where it acts as the right boundary.
The stack helps maintain increasing heights and allows quick calculation of contributions by removing taller bars when necessary. This avoids recomputation and keeps the solution efficient. The optimized approach processes each cell once, achieving O(m × n) time complexity with additional stack and DP storage.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| DP + Monotonic Stack (Histogram Technique) | O(m × n) | O(n) |
| Brute Force Expansion | O(m × n × min(m,n)) | O(1) |
take U forward
Use these hints if you're stuck. Try solving on your own first.
For each row i, create an array nums where: if mat[i][j] == 0 then nums[j] = 0 else nums[j] = nums[j-1] +1.
In the row i, number of rectangles between column j and k(inclusive) and ends in row i, is equal to SUM(min(nums[j, .. idx])) where idx go from j to k. Expected solution is O(n^3).
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, variations of this problem appear in coding interviews at top tech companies. It tests understanding of dynamic programming, matrix processing, and monotonic stack patterns commonly used in advanced array problems.
The optimal approach uses dynamic programming combined with a monotonic stack. Each row is treated as a histogram of consecutive 1s, and the stack efficiently counts valid submatrices ending at that row. This reduces the time complexity to O(m × n).
A monotonic stack helps maintain increasing histogram heights while processing columns. It allows efficient calculation of how many submatrices can be formed using each column as a boundary, avoiding repeated comparisons and improving performance.
The most common structures include arrays for storing histogram heights (dynamic programming) and a monotonic stack to track increasing column heights. These structures enable efficient counting of submatrices row by row.