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;
    }
}

All Problems

All Solutions