# 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

Java

class Solution {
public int numSubmat(int[][] mat) {
int count = 0;
int rows = mat.length, columns = mat.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;
}
}