Count Submatrices With All Ones — Problem & Solution
Count Submatrices With All Ones solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Count Submatrices With All Ones is a medium coding problem on arrays, matrix and stack, asked in Amazon and Google interviews.
- Difficulty: Medium
- Topics: Arrays, Matrix, Stack, Monotonic Stack
- Asked at: Amazon, Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
Given an m x n binary matrix mat, count its submatrices (axis-aligned rectangles of cells, of any size from 1 x 1 up to m x n) in which every cell is 1.
Example 1
Input: mat = [[1,1],[1,1]]
Output: 9
Explanation: Four 1×1, two 1×2, two 2×1 and one 2×2.
Example 2
Input: mat = [[1,0,1],[0,1,1]]
Output: 6
Explanation: Four 1×1, the 1×2 in the bottom row and the 2×1 in the last column.
Example 3
Input: mat = [[0]]
Output: 0
Constraints
1 <= m, n <= 150mat[i][j] is 0 or 1
Hints for Count Submatrices With All Ones
Hint 1
Count rectangles by their bottom-right corner. Fix the bottom row and look up: each column has a height of consecutive 1s ending at that row.
Hint 2
For bottom-right corner
(r, c), the number of all-ones rectangles is the sum over left columnsk <= cofmin(h[k..c]).Hint 3
That running-minimum sum is what a monotonic stack computes: with
pthe previous column whose height is smaller thanh[c],count[c] = count[p] + h[c] × (c - p).
How to solve Count Submatrices With All Ones
Turn each row into a histogram of upward runs of 1s; the rectangles with their bottom-right corner at (r, c) number Σ min(h[k..c]) over left edges k, which a monotonic stack maintains in O(1) amortised per cell.
Approach
- Keep
h[c], the number of consecutive 1s ending at the current row in columnc(reset to 0 on a 0). - For each row, sweep the columns left to right with a stack of column indices of strictly increasing height.
- Pop while the top's height is
>= h[c]. If a columnpremains,count[c] = count[p] + h[c] × (c - p); otherwisecount[c] = h[c] × (c + 1). - Add
count[c]to the total and pushc.
Why it works
A rectangle with bottom-right corner (r, c) and left column k can be any height up to min(h[k..c]), so that is how many there are. For left columns between p + 1 and c the minimum is h[c] itself (they are all at least as tall), giving h[c] × (c - p); for left columns <= p the minimum over [k, c] equals the minimum over [k, p] because h[p] < h[c], which is exactly count[p].
Complexity
- Time —
O(m · n) - Space —
O(n)
Pitfalls
- Counting only squares, or only full-width rows, misses most rectangles.
- Reset
h[c]to 0 on a 0 cell — heights are consecutive runs, not column totals. - An O(m² · n²) enumeration with prefix sums is correct but too slow at 150 × 150.
Reference solution
Python
from typing import List
def numSubmat(mat: List[List[int]]) -> int:
m, n = len(mat), len(mat[0])
h = [0] * n
total = 0
for r in range(m):
for c in range(n):
h[c] = h[c] + 1 if mat[r][c] == 1 else 0
cnt = [0] * n
st = []
for c in range(n):
while st and h[st[-1]] >= h[c]:
st.pop()
if st:
p = st[-1]
cnt[c] = cnt[p] + h[c] * (c - p)
else:
cnt[c] = h[c] * (c + 1)
total += cnt[c]
st.append(c)
return totalJava
public static int numSubmat(int[][] mat) {
int m = mat.length, n = mat[0].length;
int[] h = new int[n], cnt = new int[n], st = new int[n];
int total = 0;
for (int r = 0; r < m; r++) {
for (int c = 0; c < n; c++) h[c] = mat[r][c] == 1 ? h[c] + 1 : 0;
int top = 0;
for (int c = 0; c < n; c++) {
while (top > 0 && h[st[top - 1]] >= h[c]) top--;
if (top > 0) {
int p = st[top - 1];
cnt[c] = cnt[p] + h[c] * (c - p);
} else {
cnt[c] = h[c] * (c + 1);
}
total += cnt[c];
st[top++] = c;
}
}
return total;
}C++
int numSubmat(vector<vector<int>>& mat) {
int m = mat.size(), n = mat[0].size();
vector<int> h(n, 0), cnt(n, 0), st;
int total = 0;
for (int r = 0; r < m; r++) {
for (int c = 0; c < n; c++) h[c] = mat[r][c] == 1 ? h[c] + 1 : 0;
st.clear();
for (int c = 0; c < n; c++) {
while (!st.empty() && h[st.back()] >= h[c]) st.pop_back();
if (!st.empty()) {
int p = st.back();
cnt[c] = cnt[p] + h[c] * (c - p);
} else {
cnt[c] = h[c] * (c + 1);
}
total += cnt[c];
st.push_back(c);
}
}
return total;
}JavaScript
var numSubmat = function(mat) {
var m = mat.length, n = mat[0].length;
var h = new Array(n).fill(0);
var total = 0;
for (var r = 0; r < m; r++) {
for (var c = 0; c < n; c++) h[c] = mat[r][c] === 1 ? h[c] + 1 : 0;
var cnt = new Array(n).fill(0);
var st = [];
for (var c2 = 0; c2 < n; c2++) {
while (st.length > 0 && h[st[st.length - 1]] >= h[c2]) st.pop();
if (st.length > 0) {
var p = st[st.length - 1];
cnt[c2] = cnt[p] + h[c2] * (c2 - p);
} else {
cnt[c2] = h[c2] * (c2 + 1);
}
total += cnt[c2];
st.push(c2);
}
}
return total;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Matrix and Grid Traversal