1402. Count Square Submatrices With All Ones¶

Difficulty: Medium

1402. Count Square Submatrices with All Ones

Medium

Given a m * n matrix of ones and zeros, return how many square submatrices have all ones.

Example 1:

Input: matrix =
[
  [0,1,1,1],
  [1,1,1,1],
  [0,1,1,1]
]
Output: 15
Explanation: 
There are 10 squares of side 1.
There are 4 squares of side 2.
There is  1 square of side 3.
Total number of squares = 10 + 4 + 1 = 15.

Example 2:

Input: matrix = 
[
  [1,0,1],
  [1,1,0],
  [1,1,0]
]
Output: 7
Explanation: 
There are 6 squares of side 1.  
There is 1 square of side 2. 
Total number of squares = 6 + 1 = 7.

Constraints:

1 <= arr.length <= 300
1 <= arr[0].length <= 300
0 <= arr[i][j] <= 1

Solution¶

class Solution {
    private int prefix[][];
    public int countSquares(int[][] matrix) {
        int n = matrix.length;
        int m = matrix[0].length;
        prefix = new int[n + 1][m + 1];
        build(matrix);
        int count = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (matrix[i][j] == 1) {
                    int x1 = i, y1 = j, x2 = i, y2 = j;
                    while (x2 < n && y2 < m) {
                        int reqArea = (y2 - y1 + 1) * (x2 - x1 + 1);
                        if (query(x1 + 1, y1 + 1, x2 + 1, y2 + 1) == reqArea) 
                            count++;
                        x2++; y2++;
                    }
                }
            }
        }
        return count;
    }
    private int query(int x1, int y1, int x2, int y2) {
        return prefix[x2][y2] + prefix[x1 - 1][y1 - 1] - prefix[x1 - 1][y2] - prefix[x2][y1 - 1];
    }
    private void build(int matrix[][]) {
        int n = matrix.length;
        int m = matrix[0].length;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                prefix[i][j] = matrix[i - 1][j - 1] + prefix[i][j - 1] + prefix[i - 1][j] - prefix[i - 1][j - 1];
            }
        }
    }
}

Complexity Analysis¶

Time Complexity: O(?)
Space Complexity: O(?)

Approach¶

Detailed explanation of the approach will be added here