Question
Formatted question description: https://leetcode.ca/all/1504.html
1504. Count Submatrices With All Ones
Given a rows * columns matrix mat of ones and zeros, return how many submatrices 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.
Example 3:
Input: mat = [[1,1,1,1,1,1]]
Output: 21
Example 4:
Input: mat = [[1,0,1],[0,1,0],[1,0,1]]
Output: 5
Constraints:
1 <= rows <= 150
1 <= columns <= 150
0 <= mat[i][j] <= 1
Algorithm
Then traverse the matrix and count the number of matrices with i and j as the lower right corner,
Since we can know the number of consecutive 1s ending in i, j through the rows array, k is from the i-th row to the 0th row, and we can find the ones that meet the conditions one by one, where rows[k][j] and rows[i][j] enclose the rectangle number min(rows[k][j],rows[i][j])
2d array can be improved to be 1d array.
Code
Java
public class Count_Submatrices_With_All_Ones {
class Solution {
public int numSubmat(int[][] mat) {
int m = mat.length, n = mat[0].length, height[] = new int[n], res = 0;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
height[j] = mat[i][j] == 0 ? 0 : height[j] + 1; // horizontal height of histogram;
for (int k = j, min = height[j]; k >= 0 && min > 0; k--) {
min = Math.min(min, height[k]);
res += min;
}
}
}
return res;
}
}
}
Java
class Solution {
public int numSubmat(int[][] mat) {
int count = 0;
int rows = mat.length, columns = mat[0].length;
for (int i = 0; i < rows; i++) {
for (int j = 0; j < columns; j++) {
if (mat[i][j] == 1) {
int maxPossible = columns - 1;
for (int k = i; k < rows; k++) {
int maxColumn = j - 1;
for (int m = j; m <= maxPossible; m++) {
if (mat[k][m] == 1)
maxColumn = m;
else {
maxPossible = Math.min(maxPossible, maxColumn);
break;
}
}
int curColumns = maxColumn - j + 1;
int curCount = curColumns;
count += curCount;
}
}
}
}
return count;
}
}