Count Square Submatrices with All Ones LeetCode solution in Java

1
class Solution {
2
  public int countSquares(int[][] matrix) {
3
    int n = matrix.length;
4
    int m = matrix[0].length;
5
    int dp[][] = new int[n][m];
6
    for (int i = 0; i < n; i++) {
7
      dp[i][0] = matrix[i][0];
8
    }
9
    for (int i = 0; i < m; i++) {
10
      dp[0][i] = matrix[0][i];
11
    }
12
    for (int i = 1; i < n; i++) {
13
      for (int j = 1; j < m; j++) {
14
        if (matrix[i][j] == 1)
15
          dp[i][j] = 1 + Math.min(dp[i - 1][j - 1], Math.min(dp[i][j - 1], dp[i - 1][j]));
16
      }
17
    }
18

19
    int sum = 0;
20
    for (int i = 0; i < n; i++) {
21
      for (int j = 0; j < m; j++) {
22
        sum += dp[i][j];
23
      }
24
    }
25

26
    return sum;
27
  }
28
}