🌟 Find All Square Submatrices in One Clever Trick 💯🔥
\n\n## \uD83C\uDF1F Access Daily LeetCode Solutions Repo : click here\n\n---\n\n\n\n---\n\n# Intuition\nTo solve this problem, we need to count all square subma
![github_promotion_dark.png](https://assets.leetcode.com/users/images/0574b573-2fd0-4827-b06d-9bc59438c5bb_1729995808.37559.png)\n\n## **\uD83C\uDF1F Access Daily LeetCode Solutions Repo :** [click here](https://github.com/withaarzoo/LeetCode-Solutions)\n\n---\n\n![image.png](https://assets.leetcode.com/users/images/7872d5fa-e436-43eb-b931-dd49e23f4645_1729995627.4634407.png)\n\n---\n\n# Intuition\nTo solve this problem, we need to count all square submatrices made entirely of `1`s in a given binary matrix. Our first thought is that each `1` in the matrix could potentially be the bottom-right corner of a square submatrix. This leads us to consider a dynamic programming (DP) approach, where each cell in a DP table keeps track of the largest square submatrix ending at that position. This way, we can incrementally build solutions for larger squares based on smaller ones, making the solution efficient and straightforward.\n\n---\n\n# Approach\n1. **DP Table Setup**: We\'ll create a DP array `dp[i][j]` where each entry represents the side length of the largest square submatrix with all `1`s that ends at cell `(i, j)`.\n2. **Recurrence Relation**:\n   - If `matrix[i][j] == 1`, we calculate `dp[i][j]` as `min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1`. This is because the square size can only grow if the cells directly above, to the left, and diagonally up-left are also part of a square submatrix.\n   - If `matrix[i][j] == 0`, we set `dp[i][j] = 0`.\n3. **Boundary Cells**: For cells in the first row or first column, if they contain `1`, they can only form 1x1 squares, so `dp[i][j] = matrix[i][j]`.\n4. **Summing Squares**: The value in `dp[i][j]` for each cell represents the side length of the square submatrix ending at that cell. Summing all values in the `dp` table gives the total count of square submatrices.\n\n---\n\n# Complexity\n- **Time Complexity**: \\( O(m \\times n) \\), where `m` is the number of rows and `n` is the number of columns, as we only iterate through each cell once.\n- **Space Complexity**: \\( O(m \\times n) \\) for the `dp` array, though we could optimize to \\( O(n) \\) by using a single row.\n\n---\n\n# Code\n```C++ []\n#include <vector>\n#include <algorithm>\n\nclass Solution {\npublic:\n    int countSquares(std::vector<std::vector<int>>& matrix) {\n        int m = matrix.size();\n        int n = matrix[0].size();\n        std::vector<std::vector<int>> dp(m, std::vector<int>(n, 0));\n        int totalSquares = 0;\n\n        for (int i = 0; i < m; ++i) {\n            for (int j = 0; j < n; ++j) {\n                if (matrix[i][j] == 1) {\n                    if (i == 0 || j == 0) {\n                        dp[i][j] = 1;\n                    } else {\n                        dp[i][j] = std::min({dp[i-1][j], dp[i][j-1], dp[i-1][j-1]}) + 1;\n                    }\n                    totalSquares += dp[i][j];\n                }\n            }\n        }\n\n        return totalSquares;\n    }\n};\n\n```\n```Java []\nclass Solution {\n    public int countSquares(int[][] matrix) {\n        int m = matrix.length;\n        int n = matrix[0].length;\n        int[][] dp = new int[m][n];\n        int totalSquares = 0;\n\n        for (int i = 0; i < m; i++) {\n            for (int j = 0; j < n; j++) {\n                if (matrix[i][j] == 1) {\n                    if (i == 0 || j == 0) {\n                        dp[i][j] = 1;\n                    } else {\n                        dp[i][j] = Math.min(Math.min(dp[i-1][j], dp[i][j-1]), dp[i-1][j-1]) + 1;\n                    }\n                    totalSquares += dp[i][j];\n                }\n            }\n        }\n\n        return totalSquares;\n    }\n}\n\n```\n```JavaScript []\n/**\n * @param {number[][]} matrix\n * @return {number}\n */\nvar countSquares = function(matrix) {\n    const m = matrix.length;\n    const n = matrix[0].length;\n    const dp = Array.from({ length: m }, () => Array(n).fill(0));\n    let totalSquares = 0;\n\n    for (let i = 0; i < m; i++) {\n        for (let j = 0; j < n; j++) {\n            if (matrix[i][j] === 1) {\n                if (i === 0 || j === 0) {\n                    dp[i][j] = 1;\n                } else {\n                    dp[i][j] = Math.min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1;\n                }\n                totalSquares += dp[i][j];\n            }\n        }\n    }\n\n    return totalSquares;\n};\n\n```\n```Python []\nclass Solution:\n    def countSquares(self, matrix: List[List[int]]) -> int:\n        m, n = len(matrix), len(matrix[0])\n        dp = [[0] * n for _ in range(m)]\n        total_squares = 0\n\n        for i in range(m):\n            for j in range(n):\n                if matrix[i][j] == 1:\n                    if i == 0 or j == 0:\n                        dp[i][j] = 1\n                    else:\n                        dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1\n                    total_squares += dp[i][j]\n\n        return total_squares\n\n```\n```Go []\nfunc countSquares(matrix [][]int) int {\n    m := len(matrix)\n    n := len(matrix[0])\n    dp := make([][]int, m)\n    for i := range dp {\n        dp[i] = make([]int, n)\n    }\n    totalSquares := 0\n\n    for i := 0; i < m; i++ {\n        for j := 0; j < n; j++ {\n            if matrix[i][j] == 1 {\n                if i == 0 || j == 0 {\n                    dp[i][j] = 1\n                } else {\n                    dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1\n                }\n                totalSquares += dp[i][j]\n            }\n        }\n    }\n\n    return totalSquares\n}\n\nfunc min(a, b, c int) int {\n    if a < b && a < c {\n        return a\n    }\n    if b < c {\n        return b\n    }\n    return c\n}\n\n```\n\n---\n\n# Step-by-Step Detailed Explanation\n\n1. **Initialize DP Array**: We create a DP array `dp`, where each entry `dp[i][j]` holds the maximum side length of a square ending at `(i, j)` with all `1`s.\n2. **Fill DP Array**: \n   - For each cell `(i, j)` in the matrix:\n     - If it\'s on the first row or first column, it can only be a 1x1 square if it contains `1`, so we set `dp[i][j] = matrix[i][j]`.\n     - Otherwise, if `matrix[i][j] == 1`, `dp[i][j]` is set to `min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1`.\n3. **Sum Up Values**: Each entry in `dp` represents the number of squares that end at that position, so summing up all values gives us the total count of square submatrices.\n\n---\n\n![upvote_cat.png](https://assets.leetcode.com/users/images/7a38012a-9c89-46ad-8d96-af18ebca94d6_1729995876.1916063.png)\n
['Array', 'Dynamic Programming', 'Matrix', 'Python', 'C++', 'Java', 'Go', 'Python3', 'JavaScript']