1504. Count Submatrices With All Ones

Link

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

Solution

This one is tricky.

The main idea is to compress the array to something we are able to handle. ( one dimension array case)

 public int helper(int[] arr){
        int length = 0, res = 0;
        for(int i = 0; i < arr.length; i++){
            length = (arr[i] != 0) ? length+1:0;
            res += length;
        }
        return res;
    }

To aggregate every sub-array ( from row i to row j ) to one row array to apply the helper function

  public int numSubmat(int[][] mat) {
        int ret = 0;
        int M = mat.length, N = mat[0].length;
        for(int i = 0; i < M; i++){
            int[] compress = new int[N];
            Arrays.fill(compress, 1);
            
            for(int j = i; j < M; j++){
                for(int k = 0; k < N; k++) compress[k] &= mat[j][k];
                ret += helper(compress);   
            }
        }

        return ret;
    }