Count square submatrices with all ones - Easy and Unique Solution -> 🌟Nice Explanation🌟
Intuition\n- Proceed from i value is equal to 1 and j value is equal to 1 and then iterate till the end of rows and cols.\n\n- If the minimum of the three eleme
# Intuition\n- Proceed from i value is equal to 1 and j value is equal to 1 and then iterate till the end of rows and cols.\n\n- If the minimum of the three elements are non-zero, then that forms an square and this can be done while **matrix[i][j] = 1** , hence that element is itself a square of length 1.\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach\n\n**Initialization**:\n\nFind number of rows and columns in the matrix ie. dimensions of the matrix -> rows by matrix length and cols by one row\'s length.\n\n    int rows=matrix.length;\n    int cols=matrix[0].length;\n\n**Find the square of length greater than 1**:\n\nFirst , we have to iterate from 1 to rows and also from 1 to cols to meet all the elements of the row and column except the element that is either first row or it\'s first column.\n\n    for(int i=1;i<rows;i++) for(int j=1;j<cols;j++)\n   \n   If the value of an element is equal to 1 , then we\'re going to check its left(i,j-1) , top(i-1,j) and top left(i-1,j-1) value by finding minimum of all those and adding to matrix[i][j].\n\n    \n\n   so the value of matrix[i][j] becomes 2 if it forms square (ie. result of minimum is non-zero) and other to represent the element itself which is of length 1.\n\n    if(matrix[i][j]==1)\n    {\n        matrix[i][j]+=Math.min(matrix[i-1][j],Math.min(matrix[i][j-1],matrix[i-1][j-1]));\n    }\n\n**Finding total number of squares possible**:\n\n   Now , the total number of squares possible can be found by adding all the elements in the matrix , since at each stage in the matrix -> number of possible square is individually noted using dynamic programming approach.\n\n    int total=0;\n        for(int i=0;i<rows;i++)\n        {\n            for(int j=0;j<cols;j++)\n            {\n                total+=matrix[i][j];\n            }\n        }\n\n**Returning the total**:\n\n   Return the total which gives the total number of square submatrices possible which contains all the elements as ones.\n\n    return total;\n\n\n<!-- Describe your approach to solving the problem. -->\n\n# Complexity\n- ***Time complexity***: **O(mxn)**.\n    m -> number of rows in the matrix.\n    n -> number of columns in the matrix.\n\n**DP Update (Nested loop)** : **O(mxn)**.\n  1. The nested loop iterates over each cell of matrix from 1 to rows and from 1 to cols, and the operation performed inside the nested loop takes the complexity of O(1).\n\n  1. Hence the operation takes place **O(mxn) time** .So it takes O(mxn) time complexity.\n\n**Counting total Squares(Nested loop)**: **O(mxn)**.\n   1. After updating the matrix, another nested loop iterates over every cell to calculate the total number of squares by summing up all the values in the matrix.\n   \n  1. This step also takes **O(m\xD7n) time**, as each cell is visited once to accumulate the count.\n\n**Total Time Complexity**:\n   - The overall time complexity will be O(mxn) + O(mxn) = **O(mxn)**.\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- ***Space complexity***: **O(1)**.\n\n**In-place modification**: **O(1)**.\n   1. The program uses the input **matrix itself** to store the intermediate DP values instead of creating an additional dp matrix.\n1. No extra space proportional to the size of the input is required, so the auxiliary space complexity for this part **O(1)**.\n\n**Other variables**: **O(1)**.\n   1. Only a few scalar variables (rows, cols, total, and loop variables) are used, which **require constant space**.\n\n**Total Space Complexity**: **O(1)**.\n  - The overall space complexity is **O(1)**, considering only a **constant amount of extra space** is used.\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```java []\nclass Solution {\n    public int countSquares(int[][] matrix) {\n        //Find no of rows and columns\n        int rows=matrix.length;\n        int cols=matrix[0].length;\n\n        for(int i=1;i<rows;i++)\n        {\n            for(int j=1;j<cols;j++)\n            {\n                if(matrix[i][j]==1)\n                {\n                    matrix[i][j]+=Math.min(matrix[i-1][j],Math.min(matrix[i][j-1],matrix[i-1][j-1]));\n                }\n            }\n        }\n\n        //Number of squares possible\n        int total=0;\n        for(int i=0;i<rows;i++)\n        {\n            for(int j=0;j<cols;j++)\n            {\n                total+=matrix[i][j];\n            }\n        }\n        return total;\n    }\n}\n```
['Array', 'Dynamic Programming', 'Matrix', 'Java']