11package com .fishercoder .solutions ;
22
3- /**
4- * 1277. Count Square Submatrices with All Ones
5- *
6- * Given a m * n matrix of ones and zeros, return how many square submatrices have all ones.
7- *
8- * Example 1:
9- * Input: matrix =
10- * [
11- * [0,1,1,1],
12- * [1,1,1,1],
13- * [0,1,1,1]
14- * ]
15- * Output: 15
16- * Explanation:
17- * There are 10 squares of side 1.
18- * There are 4 squares of side 2.
19- * There is 1 square of side 3.
20- * Total number of squares = 10 + 4 + 1 = 15.
21- *
22- * Example 2:
23- * Input: matrix =
24- * [
25- * [1,0,1],
26- * [1,1,0],
27- * [1,1,0]
28- * ]
29- * Output: 7
30- * Explanation:
31- * There are 6 squares of side 1.
32- * There is 1 square of side 2.
33- * Total number of squares = 6 + 1 = 7.
34- *
35- * Constraints:
36- * 1 <= arr.length <= 300
37- * 1 <= arr[0].length <= 300
38- * 0 <= arr[i][j] <= 1
39- * */
403public class _1277 {
414public static class Solution1 {
425/**
436 * In-place solution.
44- *
457 * credit: https://leetcode.com/problems/count-square-submatrices-with-all-ones/discuss/441306/Python-DP-solution
46- * * /
8+ */
479public int countSquares (int [][]matrix ) {
4810int m =matrix .length ;
4911int n =matrix [0 ].length ;
@@ -63,7 +25,6 @@ public int countSquares(int[][] matrix) {
6325public static class Solution2 {
6426/**
6527 * Use m*n extra space solution.
66- *
6728 * credit: https://leetcode.com/problems/count-square-submatrices-with-all-ones/discuss/441312/Java-Simple-DP-solution
6829 */
6930public int countSquares (int [][]matrix ) {