LeetCode [1277] Count Square Submatrices with All Ones

 1277. 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

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21

class Solution { public int countSquares(int[][] matrix) { int m = matrix.length, n = matrix[0].length; int[][] preSum = new int[m+1][n+1]; int[][] dp = new int[m+1][n+1]; for(int i=1; i<=m; ++i){ for(int j=1; j<=n; ++j){ preSum[i][j] = preSum[i-1][j] + preSum[i][j-1] - preSum[i-1][j-1] + matrix[i-1][j-1]; dp[i][j] = dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1]; int min = Math.min(i, j); for(int l=1; l<=min; ++l){ int s = preSum[i][j]-preSum[i-l][j]-preSum[i][j-l]+preSum[i-l][j-l]; if(s==l*l) dp[i][j]++; else break; } } } return dp[m][n]; } }

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

class Solution { public int countSquares(int[][] matrix) { int count=0; for(int i=0;i<matrix.length;i++){ for(int j=0;j<matrix[0].length;j++){ if(matrix[i][j]==1 && i-1>=0 && j-1>=0){ matrix[i][j]+=Math.min(matrix[i-1][j], Math.min(matrix[i-1][j-1], matrix[i][j-1])); } //System.out.println(" i: "+i+" j: "+j+" val: "+matrix[i][j]); count+=matrix[i][j]; } } return count; } }