LeetCode [1540] Count Submatrices With All Ones

 1504. Count Submatrices With All Ones

Medium

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

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27

class Solution { int oneD(int[] array){ int ret = 0, len = 0; for(int i=0; i<array.length; ++i){ if(array[i]==0) len = 0; else len++; ret += len; } return ret; } public int numSubmat(int[][] mat) { int m = mat.length, n = mat[0].length; int ret = 0; for(int i=0; i<m; ++i){ int[] r = new int[n]; Arrays.fill(r, 1); for(int j=i; j<m; ++j){ for(int k=0; k<n; ++k){ r[k] &= mat[j][k]; } ret += oneD(r); } } return ret; } }

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30

class Solution { int helper(int[] row){ Stack<Integer> stk = new Stack<>();//mono increasing stk int[] sum = new int[row.length]; int total = 0; for(int i=0; i<row.length; ++i){ while(!stk.isEmpty() && row[stk.peek()]>=row[i]) stk.pop(); int preIndex = stk.isEmpty()?-1:stk.peek(); int s = row[i]*(i-preIndex); sum[i] = s + (preIndex<0?0:sum[preIndex]); total += sum[i]; stk.push(i); } return total; } public int numSubmat(int[][] mat) { int m = mat.length, n = mat[0].length; int ret = 0; int[] row = new int[n]; for(int i=0; i<m; ++i){ for(int j=0; j<n; ++j){ if(mat[i][j]==0) row[j] = 0; else row[j]++; } ret += helper(row); } return ret; } }