Leetcode•Oct 02, 2026
Count Submatrices With All Ones
Hazrat Ali
Leetcode
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.
Solution
var numSubmat = function(mat) {
const m = mat.length;
const n = mat[0].length;
const heights = new Array(n).fill(0);
let answer = 0;
for (let i = 0; i < m; i++) {
for (let j = 0; j < n; j++) {
if (mat[i][j] === 1) {
heights[j]++;
} else {
heights[j] = 0;
}
}
const stack = [];
const dp = new Array(n).fill(0);
for (let j = 0; j < n; j++) {
while (
stack.length > 0 &&
heights[stack[stack.length - 1]] >= heights[j]
) {
stack.pop();
}
if (stack.length === 0) {
dp[j] = heights[j] * (j + 1);
} else {
const prev = stack[stack.length - 1];
dp[j] = dp[prev] + heights[j] * (j - prev);
}
stack.push(j);
answer += dp[j];
}
}
return answer;
};