[Java/Python] 4 solutions - Clean & Concise - O(M*N)
\u2714\uFE0F Solution 1: Prefix Sum in the Matrix\njava\nclass Solution {\n    int[][] prefixSum;\n    int m, n;\n    public int countSquares(int[][] mat) {\n  
**\u2714\uFE0F Solution 1: Prefix Sum in the Matrix**\n```java\nclass Solution {\n    int[][] prefixSum;\n    int m, n;\n    public int countSquares(int[][] mat) {\n        m = mat.length; n = mat[0].length;\n        prefixSum = new int[m+1][n+1];\n        for (int r = 0; r < m; ++r) {\n            for (int c = 0; c < n; ++c) {\n                prefixSum[r+1][c+1] = prefixSum[r][c+1] + prefixSum[r+1][c] - prefixSum[r][c] + mat[r][c];\n            }\n        }\n        int ans = 0;\n        for (int k = 1; k < Math.min(m, n) + 1; ++k)  {\n            ans += cntValid(k);\n        }\n        return ans;\n    }\n\n    int cntValid(int size) {\n        int ans = 0;\n        for (int r = 0; r < m - size + 1; ++r) {\n            for (int c = 0; c < n - size + 1; ++c) {\n                int r2 = r+size-1;\n                int c2 = c + size - 1;\n                if (getSum(r, c, r2, c2) == size * size)\n                    ans += 1;\n            }\n        }\n        return ans;\n    }\n\n    int getSum(int r1, int c1, int r2, int c2) {\n        return prefixSum[r2+1][c2+1] - prefixSum[r2+1][c1] - prefixSum[r1][c2+1] + prefixSum[r1][c1];\n    }\n}\n```\nComplexity:\n- Time: `O(M^2 * N)`, where `M` is the minimum and `N` is the maxmimum between number of rows and number of columns in the matrix.\n- Space: `O(M * N)`\n---\n**\u2714\uFE0F Solution 2: Naive Dynamic Programming**\n- Let `dp[r][c][l]` denote if the square has bottom right in cell `(r, c)` with side length `l` is an valid square or not.\n```java\nclass Solution {\n    public int countSquares(int[][] matrix) {\n        int m = matrix.length, n = matrix[0].length;\n        boolean[][][] dp = new boolean[m][n][Math.min(m, n)];\n\n        int ans = 0;\n        for (int r = 0; r < m; ++r) {\n            for (int c = 0; c < n; ++c) {\n                if (matrix[r][c] == 0) continue;\n                int size = Math.min(r, c) + 1;\n                for (int l = 0; l < size; ++l) {\n                    if (l == 0) {\n                        dp[r][c][l] = matrix[r][c] == 1;\n                    } else {\n                        int dr = r - l;\n                        int dc = c - l;\n                        dp[r][c][l] = dr >= 0 && dc >= 0 && matrix[dr][dc] == 1 && dp[r-1][c][l-1] && dp[r][c-1][l-1];\n                    }\n\n                    if (dp[r][c][l]) {\n                        ans += 1;\n                    }\n                }\n            }\n        }\n        return ans;\n    }\n}\n```\nComplexity:\n- Time: `O(M^2 * N)`, where `M` is the minimum and `N` is the maxmimum between number of rows and number of columns in the matrix.\n- Space: `O(M * N)`\n\n---\n**\u2714\uFE0F Solution 3: Dynamic Programming**\n- Let `dp[r][c]` is the largest size of square that has bottom right at `mat[r][c]`, it\'s also the number of sub-squares.\n```python\nclass Solution:\n    def countSquares(self, mat: List[List[int]]) -> int:\n        m, n = len(mat), len(mat[0])\n        dp = [[0] * n for _ in range(m)]\n        ans = 0\n        for r in range(m):\n            for c in range(n):\n                if r == 0 or c == 0:\n                    dp[r][c] = mat[r][c]\n                elif mat[r][c] == 1:\n                    dp[r][c] = min(dp[r-1][c], min(dp[r][c-1], dp[r-1][c-1])) + 1\n                ans += dp[r][c]\n        return ans\n```\nComplexity:\n- Time: `O(M * N)`, where `M` is the number of rows, `N` is the number of columns in the matrix.\n- Space: `O(M * N)`\n---\n**\u2714\uFE0F Solution 4: DP with Space Optimized**\n- Since we build `dp` row by row and we only need to access the **current row dp** and **previous row dp**, so we can just use **dp, dpPrev** to store dp values of 2 latest rows.\n```python\nclass Solution:\n    def countSquares(self, mat: List[List[int]]) -> int:\n        m, n = len(mat), len(mat[0])\n        dp, dpPrev = [0] * n, [0] * n\n        ans = 0\n        for r in range(m):\n            for c in range(n):\n                if r == 0 or c == 0:\n                    dp[c] = mat[r][c]\n                elif mat[r][c] == 1:\n                    dp[c] = min(dpPrev[c], min(dp[c-1], dpPrev[c-1])) + 1\n                else:\n                    dp[c] = 0\n                ans += dp[c]\n            dp, dpPrev = dpPrev, dp\n        return ans\n```\nComplexity:\n- Time: `O(M * N)`, where `M` is the number of rows, `N` is the number of columns in the matrix.\n- Space: `O(N)`
[]