Count Submatrices With All Ones solution and explanation
Google
9 more videos on this problem
Leetcode 1504. Count Submatrices With All OnesFraz · 10:16 · 35K views
Count Submatrices With All Ones | Detailed Explanation | Leetcode 1504 | codestorywithMIKcodestorywithMIK · 29:31 · 13K views
Count Submatrices With All Ones | Leetcode 1504 | Monotonic StackTechdose · 34:12 · 6K views
LeetCode 1504. Count Submatrices With All OnesHappy Coding · 27:38 · 6K views
Count Submatrics with all 1s | Dynamic Programming | Leetcode#1504Joey'sTech · 11:01 · 4K views
1504. Count Submatrices With All Ones | Leetcode Daily - PythonLeetcode Daily · 6:51 · 2K views
Daily Leetcode #1969: Aug 21, 2025 - 1504. Count Submatrices With All OnesProgramming Live with Larry · 18:17 · 777 views
Count Submatrices With All Ones | LeetCode 1504 | Histogram | Array | DP | Asked in GoogleCode Harmony · 39:05 · 597 views
1504.Count Submatrices With All Ones|leetcode dp series|leetcodeDp wale · 11:39 · 593 views
Count Submatrices With All Ones | LeetCode 1504 | DP + Histogram Approach ExplainedcodingX krishna · 23:55 · 228 views
The problem
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 either0or1.
Approach overview
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.
Approach 1: Histogram Approach
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.
def numSubmat(mat):
m, n = len(mat), len(mat[0])
result = 0
for r in range(m):
height = [0] * n
for i in range(r, m):
for j in range(n):
if mat[i][j] == 0:
height[j] = 0
else:
height[j] += 1
result += countSubmatrices(height)
return result
def countSubmatrices(height):
stack = []
current_sum = 0
total = 0
for h in height:
sum_height = 0
while stack and stack[-1][0] >= h:
prev_h, prev_sum = stack.pop()
current_sum -= prev_sum
sum_height = h * (len(stack) + 1)
current_sum += sum_height
stack.append((h, sum_height))
total += current_sum
return total
# Example usage:
mat = [[1, 0, 1], [1, 1, 0], [1, 1, 0]]
print(numSubmat(mat)) # Output: 13public int numSubmat(int[][] mat) {
int m = mat.length, n = mat[0].length;
int result = 0;
for (int r = 0; r < m; r++) {
int[] height = new int[n];
for (int i = r; i < m; i++) {
for (int j = 0; j < n; j++) {
height[j] = mat[i][j] == 0 ? 0 : height[j] + 1;
}
result += countSubmatrices(height);
}
}
return result;
}
private int countSubmatrices(int[] heights) {
Stack<int[]> stack = new Stack<>();
int sum = 0, result = 0;
for (int h : heights) {
int sumHeight = 0;
while (!stack.isEmpty() && stack.peek()[0] >= h) {
sum -= stack.pop()[1];
}
sumHeight = h * (stack.isEmpty() ? 1 : stack.peek()[1] + 1);
sum += sumHeight;
stack.push(new int[]{h, sumHeight});
result += sum;
}
return result;
}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.
Approach 2: Dynamic Programming Approach
Utilize dynamic programming to store the count of submatrices ending at each position (i, j). This solution leverages cumulative sums to efficiently count submatrices.
#include <vector>
using namespace std;
int numSubmat(vector<vector<int>>& mat) {
int m = mat.size(), n = mat[0].size();
vector<vector<int>> dp(m, vector<int>(n, 0));
int result = 0;
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if (mat[i][j] == 1) {
dp[i][j] = (j == 0) ? 1 : dp[i][j-1] + 1;
int width = dp[i][j];
for (int k = i; k >= 0; --k) {
width = min(width, dp[k][j]);
if (width == 0) break;
result += width;
}
}
}
}
return result;
}
// Example usage:
// vector<vector<int>> mat = {{1, 0, 1}, {1, 1, 0}, {1, 1, 0}};
// cout << numSubmat(mat) << endl; // Output: 13function numSubmat(mat) {
const m = mat.length, n = mat[0].length;
let result = 0;
const dp = Array.from({ length: m }, () => Array(n).fill(0));
for (let i = 0; i < m; i++) {
for (let j = 0; j < n; j++) {
if (mat[i][j] === 1) {
dp[i][j] = (j === 0) ? 1 : dp[i][j - 1] + 1;
let minWidth = dp[i][j];
for (let k = i; k >= 0; k--) {
minWidth = Math.min(minWidth, dp[k][j]);
if (minWidth === 0) break;
result += minWidth;
}
}
}
}
return result;
}
// Example usage:
// const mat = [[1, 0, 1], [1, 1, 0], [1, 1, 0]];
// console.log(numSubmat(mat)); // Output: 13This 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.
Time Complexity: O(m * n^2), Space Complexity: O(m*n).
Approach 3: Enumeration + Prefix Sum
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.
function numSubmat(mat: number[][]): number {
const m = mat.length;
const n = mat[0].length;
const g: number[][] = Array.from({ length: m }, () => Array(n).fill(0));
for (let i = 0; i < m; i++) {
for (let j = 0; j < n; j++) {
if (mat[i][j]) {
g[i][j] = j === 0 ? 1 : 1 + g[i][j - 1];
}
}
}
let ans = 0;
for (let i = 0; i < m; i++) {
for (let j = 0; j < n; j++) {
let col = Infinity;
for (let k = i; k >= 0; k--) {
col = Math.min(col, g[k][j]);
ans += col;
}
}
}
return ans;
}func numSubmat(mat [][]int) (ans int) {
m, n := len(mat), len(mat[0])
g := make([][]int, m)
for i := range g {
g[i] = make([]int, n)
for j := range g[i] {
if mat[i][j] == 1 {
if j == 0 {
g[i][j] = 1
} else {
g[i][j] = 1 + g[i][j-1]
}
}
}
}
for i := range g {
for j := range g[i] {
col := 1 << 30
for k := i; k >= 0 && col > 0; k-- {
col = min(col, g[k][j])
ans += col
}
}
}
return
}impl Solution {
pub fn num_submat(mat: Vec<Vec<i32>>) -> i32 {
let m = mat.len();
let n = mat[0].len();
let mut g = vec![vec![0; n]; m];
for i in 0..m {
for j in 0..n {
if mat[i][j] == 1 {
if j == 0 {
g[i][j] = 1;
} else {
g[i][j] = 1 + g[i][j - 1];
}
}
}
}
let mut ans = 0;
for i in 0..m {
for j in 0..n {
let mut col = i32::MAX;
let mut k = i as i32;
while k >= 0 && col > 0 {
col = col.min(g[k as usize][j]);
ans += col;
k -= 1;
}
}
}
ans
}
}Complexity comparison
| 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 | – |
Complexity analysis
| 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. |
Frequently asked questions
Is Count Submatrices With All Ones easy or hard?
Count Submatrices With All Ones is classified as a Medium problem on LeetCode. The brute force idea is simple, but recognizing the histogram transformation and applying a monotonic stack requires solid experience with matrix and stack-based algorithms.
Count Submatrices With All Ones Python/Java solution
Python and Java implementations typically build a height array for each row and apply a monotonic stack to compute rectangle counts. Both implementations run in O(m * n) time and require only O(n) additional space.
How to solve Count Submatrices With All Ones in O(n)?
Treat every row as the base of a histogram where each column stores the height of consecutive ones. Use a monotonic increasing stack to count how many rectangles end at each column efficiently. Processing each row this way leads to an overall O(m * n) algorithm.
What is the best approach for Count Submatrices With All Ones?
The optimal approach converts each row into a histogram of consecutive vertical ones and then counts rectangles using a monotonic stack. This method processes each column once per row and achieves O(m * n) time complexity with O(n) extra space.
Is Count Submatrices With All Ones asked at Google/Amazon/Meta?
Matrix counting problems with histogram or monotonic stack patterns appear frequently in interviews at companies like Google, Amazon, and Meta. Variations of this problem are commonly used to test understanding of stacks, dynamic programming, and 2D array transformations.
What data structure is used in Count Submatrices With All Ones?
The optimal solution relies on a monotonic stack along with an array representing histogram heights. The stack maintains increasing column heights so rectangles can be counted efficiently without rechecking previous columns.
What is the time complexity of Count Submatrices With All Ones?
The optimal histogram + monotonic stack solution runs in O(m * n) time, where m is the number of rows and n is the number of columns. Each element is pushed and popped from the stack at most once per row. A simpler dynamic programming approach runs in O(m * n^2).