-
Notifications
You must be signed in to change notification settings - Fork 2
/
CountSquareSubMatricesWithAllOnes.java
71 lines (67 loc) · 1.72 KB
/
CountSquareSubMatricesWithAllOnes.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
package Leetcode;
/**
* @author kalpak
*
* 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
*
*/
public class CountSquareSubMatricesWithAllOnes {
public static int countSquares(int[][] matrix) {
int[][] dp = new int[matrix.length + 1][matrix[0].length + 1];
int result = 0;
for(int i = 0; i < matrix.length; i++) {
for(int j = 0; j < matrix[0].length; j++) {
if(matrix[i][j] == 1) {
if(i == 0 || j == 0) // 1st row or 1st column
result += 1; // The 1 cells are square on its own
else {
int val = Math.min(matrix[i - 1][j], Math.min(matrix[i - 1][j - 1], matrix[i][j - 1])) + matrix[i][j];
result += val;
matrix[i][j] = val; // memoize
}
}
}
}
return result;
}
public static void main(String[] args) {
int[][] matrix = new int[][]{{0, 1, 1, 1}, {1, 1, 1, 1}, {0, 1, 1, 1}};
System.out.println(countSquares(matrix));
}
}