Beats 100%|| Detailed explanation
\n\n\n# Problem Analysis\n###### Given a binary matrix (containing only 1s and 0s), we need to count all square submatrices that contain only 1s. Each submatrix
![image.png](https://assets.leetcode.com/users/images/3815db21-b2bd-408d-a33d-94a34dc82646_1730014210.222744.png)\n\n\n# Problem Analysis\n###### Given a binary matrix (containing only 1s and 0s), we need to count all square submatrices that contain only 1s. Each submatrix should form a square, meaning the number of rows equals the number of columns.\n\n# Solution Outline\nWe can solve this problem using dynamic programming (DP) by leveraging the properties of a square. For any cell (i, j) that contains 1, the largest square ending at that cell depends on the cells to its top, left, and top-left diagonal.\n\n# Intuition\n- If there\u2019s a 1 in a cell, it could potentially be part of a larger square.\n- For each cell (i, j), we compute the largest square ending at (i, j) by considering the minimum of three adjacent cells: (i-1, j), (i, j-1), and (i-1, j-1).\n- If any of these cells has a smaller square count, then (i, j) cannot form a larger square than that minimum value plus 1.\n\n# Approach\n1. Initialization: Initialize the matrix itself as the DP table.\n2. Iterate Over the Matrix:\n    - For each cell (i, j), if the cell value is 1, update it to the size of the largest square submatrix ending at that cell.\n    - The formula for updating is:\n     `dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1`\n3. Count Squares: Sum up the values in the matrix after updates, as each value now represents the number of square submatrices ending at that cell.\n\n\n# Complexity\n- Time complexity:\n*O(m\xD7n)*\n\n- Space complexity:\nO(1)\n\n# Code\n```python3 []\nclass Solution:\n    def countSquares(self, matrix: List[List[int]]) -> int:\n        n = len(matrix)\n        dp = matrix\n        res = 0\n\n        for r in range(len(matrix)):\n            for c in range(len(matrix[0])):\n                if dp[r][c] == 0: continue\n                if r != 0 and c != 0:\n                    if dp[r-1][c] > 0 and dp[r][c-1] > 0 and dp[r-1][c-1] > 0:\n                        dp[r][c] = min(dp[r-1][c], dp[r][c-1], dp[r-1][c-1]) + 1\n                res += dp[r][c]\n        return res\n```\n```Java []\nclass Solution {\n    public int countSquares(int[][] matrix) {\n        int rowSize = matrix.length;\n        int colSize = matrix[0].length;\n\n        for (int i = 1; i < rowSize; i++) {\n            for (int j = 1; j < colSize; j++) {\n                if (matrix[i][j] == 1) {\n                    matrix[i][j] += Math.min(matrix[i - 1][j], \n                                             Math.min(matrix[i - 1][j - 1], matrix[i][j - 1]));\n                }\n            }\n        }\n\n        int total = 0;\n        for (int i = 0; i < rowSize; i++) {\n            for (int j = 0; j < colSize; j++) {\n                total += matrix[i][j];\n            }\n        }\n\n        return total;\n    }\n}\n\n```\n```Cpp []\nclass Solution {\npublic:\n    int countSquares(vector<vector<int>>& matrix) {\n        int rowSize = matrix.size();\n        int colSize = matrix[0].size();\n\n        for (int i = 1; i < rowSize; i++) {\n            for (int j = 1; j < colSize; j++) {\n                if (matrix[i][j] == 1) {\n                    matrix[i][j] += min(matrix[i - 1][j], \n                                        min(matrix[i][j - 1], matrix[i - 1][j - 1]));\n                }\n            }\n        }\n\n        int total = 0;\n        for (int i = 0; i < rowSize; i++) {\n            for (int j = 0; j < colSize; j++) {\n                total += matrix[i][j];\n            }\n        }\n\n        return total;\n    }\n};\n\n```\n\n# Explanation of the Code\n- **Matrix Traversal:** We start traversing the matrix from (1,1) to ensure that we don\u2019t go out of bounds when accessing the top, left, or top-left cells.\n- **Updating DP Table:** Each cell in the matrix is updated to store the size of the largest square ending at that cell. This update uses values from the top, left, and top-left cells.\n- **Summing Up:** Once the matrix is updated, each cell contains the count of square submatrices ending at that cell. Summing up all cells gives the total number of square submatrices with all 1s.\n\n# Edge Cases\n- Single Element: If the matrix has only one element, handle it directly.\n- All Zeros: If the matrix has no 1s, the result is 0.\n\n# Best possible solution in terms of space complexity:\n\n```\nclass Solution:\n    def countSquares(self, matrix: List[List[int]]) -> int:\n        rows,cols = len(matrix), len(matrix[0])\n        dp = [[0]*(cols+1) for _ in range(rows+1)]\n        count = 0 \n        for r in range(rows):\n            for c in range(cols):\n                if matrix[r][c]:\n                    dp[r+1][c+1] = min(dp[r][c],dp[r+1][c],dp[r][c+1])+1\n                    count+=dp[r+1][c+1]\n        return count\n    \n```
['C++', 'Java', 'Python3']