Given a
Example 1:
Example 2:
Constraints:
1 <= arr.length <= 300 1 <= arr[0].length <= 300 0 <= arr[i][j] <= 1
Solution
Its a matrix DP problem. Every location in the matrix can have two values 0/1, If its a 0 then it can not contribute to the total squares count, if its 1 then it can.
If location having value as 1, then element itself can be consider as square, Also it can be part of other square ending at the current location, that can be calculated based on previous row and column having 1s or not.
For example
DP equation for that can be formed as
Code
0 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 |
public class CountSquareMatrix { public int countSquares(int[][] matrix) { int cnt = 0; if(matrix.length==0) return cnt; /** * Checking first column for all ones. */ for (int i = 0; i < matrix.length; i++) { if (matrix[i][0] == 1) { cnt++; } } /** * Checking first row for all ones. */ for (int i = 1; i < matrix[0].length; i++) { if (matrix[0][i] == 1) { cnt++; } } for (int i = 1; i < matrix.length; i++) { for (int j = 1; j < matrix[i].length; j++) { if (matrix[i][j] == 1) { matrix[i][j] = Math.min(matrix[i-1][j-1],Math.min(matrix[i - 1][j],matrix[i][j - 1])) + 1; cnt += matrix[i][j]; } } } return cnt; } public static void main(String[] args) { int[][] matrix = { {1,0,1}, {1,1,0}, {1,1,0}}; CountSquareMatrix csMatrix=new CountSquareMatrix(); System.out.println(csMatrix.countSquares(matrix)); } } |
Output
Complexity Analysis
Time complexity: O(M * N).Space Complexity: O(1).
We encourage you to write a comment if you have a better solution or having any doubt on the above topic.