✅ Explained step by step | Beats 100% | ✅ Working 27.10.2024
python3 []\nclass Solution:\n    def countSquares(self, matrix: List[List[int]]) -> int:\n        # Get dimensions of the matrix\n        n = len(matrix)    # n
```python3 []\nclass Solution:\n    def countSquares(self, matrix: List[List[int]]) -> int:\n        # Get dimensions of the matrix\n        n = len(matrix)    # number of rows\n        m = len(matrix[0]) # number of columns\n        \n        # Create a DP table with same dimensions as matrix\n        dp = [[0] * m for _ in range(n)]\n        \n        # Variable to store total count of squares\n        ans = 0\n        \n        # Initialize first column of DP table\n        for i in range(n):\n            dp[i][0] = matrix[i][0]\n            ans += dp[i][0]\n        \n        # Initialize first row of DP table\n        for j in range(1, m):\n            dp[0][j] = matrix[0][j]\n            ans += dp[0][j]\n        \n        # Fill the DP table for remaining cells\n        for i in range(1, n):\n            for j in range(1, m):\n                # Only process if current cell in matrix is 1\n                if matrix[i][j] == 1:\n                    # Find minimum of left, top, and diagonal cells and add 1\n                    dp[i][j] = 1 + min(dp[i][j-1], dp[i-1][j], dp[i-1][j-1])\n                ans += dp[i][j]\n        \n        return ans\n\n\n```\n```cpp []\nclass Solution {\npublic:\n    int countSquares(vector<vector<int>>& matrix) {\n        // Get dimensions of the matrix\n        int n = matrix.size();    // number of rows\n        int m = matrix[0].size(); // number of columns\n        \n        // Create a DP table with same dimensions as matrix\n        vector<vector<int>> dp(n, vector<int>(m, 0));\n        \n        // Variable to store total count of squares\n        int ans = 0;\n        \n        // Initialize first column of DP table\n        // Each cell in first column can only form a 1x1 square if matrix[i][0] = 1\n        for (int i = 0; i < n; i++) {\n            dp[i][0] = matrix[i][0];\n            ans += dp[i][0];  // Add the count of squares from the first column\n        }\n        \n        // Initialize first row of DP table\n        // Each cell in first row can only form a 1x1 square if matrix[0][j] = 1\n        for (int j = 1; j < m; j++) {\n            dp[0][j] = matrix[0][j];\n            ans += dp[0][j];  // Add the count of squares from the first row\n        }\n        \n        // Fill the DP table for remaining cells\n        for(int i = 1; i < n; i++) {\n            for(int j = 1; j < m; j++) {\n                // Only process if current cell in matrix is 1\n                if(matrix[i][j] == 1) {\n                    // For each cell, check the minimum value among:\n                    // 1. Left cell (dp[i][j-1])\n                    // 2. Top cell (dp[i-1][j])\n                    // 3. Top-left diagonal cell (dp[i-1][j-1])\n                    // Add 1 to this minimum value\n                    dp[i][j] = 1 + min({dp[i][j-1], dp[i-1][j], dp[i-1][j-1]});\n                }\n                // Add current cell\'s value to total count\n                ans += dp[i][j];\n            }\n        }\n        \n        // Return total count of squares\n        return ans;\n    }\n};\n\n```\n```java []\nclass Solution {\n    public int countSquares(int[][] matrix) {\n        // Get dimensions of the matrix\n        int n = matrix.length;    // number of rows\n        int m = matrix[0].length; // number of columns\n        \n        // Create a DP table with same dimensions as matrix\n        int[][] dp = new int[n][m];\n        \n        // Variable to store total count of squares\n        int ans = 0;\n        \n        // Initialize first column of DP table\n        for (int i = 0; i < n; i++) {\n            dp[i][0] = matrix[i][0];\n            ans += dp[i][0];\n        }\n        \n        // Initialize first row of DP table\n        for (int j = 1; j < m; j++) {\n            dp[0][j] = matrix[0][j];\n            ans += dp[0][j];\n        }\n        \n        // Fill the DP table for remaining cells\n        for(int i = 1; i < n; i++) {\n            for(int j = 1; j < m; j++) {\n                if(matrix[i][j] == 1) {\n                    dp[i][j] = 1 + Math.min(Math.min(dp[i][j-1], dp[i-1][j]), dp[i-1][j-1]);\n                }\n                ans += dp[i][j];\n            }\n        }\n        \n        return ans;\n    }\n}\n\n\n```\n```csharp []\npublic class Solution {\n    public int CountSquares(int[][] matrix) {\n        // Get dimensions of the matrix\n        int n = matrix.Length;    // number of rows\n        int m = matrix[0].Length; // number of columns\n        \n        // Create a DP table with same dimensions as matrix\n        int[][] dp = new int[n][];\n        for(int i = 0; i < n; i++) {\n            dp[i] = new int[m];\n        }\n        \n        // Variable to store total count of squares\n        int ans = 0;\n        \n        // Initialize first column of DP table\n        for (int i = 0; i < n; i++) {\n            dp[i][0] = matrix[i][0];\n            ans += dp[i][0];\n        }\n        \n        // Initialize first row of DP table\n        for (int j = 1; j < m; j++) {\n            dp[0][j] = matrix[0][j];\n            ans += dp[0][j];\n        }\n        \n        // Fill the DP table for remaining cells\n        for(int i = 1; i < n; i++) {\n            for(int j = 1; j < m; j++) {\n                if(matrix[i][j] == 1) {\n                    dp[i][j] = 1 + Math.Min(dp[i][j-1], \n                                Math.Min(dp[i-1][j], dp[i-1][j-1]));\n                }\n                ans += dp[i][j];\n            }\n        }\n        \n        return ans;\n    }\n}\n\n```\n```golang []\nfunc countSquares(matrix [][]int) int {\n    // Get dimensions of the matrix\n    n := len(matrix)    // number of rows\n    m := len(matrix[0]) // number of columns\n    \n    // Create a DP table with same dimensions as matrix\n    dp := make([][]int, n)\n    for i := range dp {\n        dp[i] = make([]int, m)\n    }\n    \n    // Variable to store total count of squares\n    ans := 0\n    \n    // Initialize first column of DP table\n    for i := 0; i < n; i++ {\n        dp[i][0] = matrix[i][0]\n        ans += dp[i][0]\n    }\n    \n    // Initialize first row of DP table\n    for j := 1; j < m; j++ {\n        dp[0][j] = matrix[0][j]\n        ans += dp[0][j]\n    }\n    \n    // Fill the DP table for remaining cells\n    for i := 1; i < n; i++ {\n        for j := 1; j < m; j++ {\n            if matrix[i][j] == 1 {\n                // Find minimum of left, top, and diagonal cells\n                min := dp[i][j-1]\n                if dp[i-1][j] < min {\n                    min = dp[i-1][j]\n                }\n                if dp[i-1][j-1] < min {\n                    min = dp[i-1][j-1]\n                }\n                dp[i][j] = 1 + min\n            }\n            ans += dp[i][j]\n        }\n    }\n    \n    return ans\n}\n```\n```swift []\nclass Solution {\n    func countSquares(_ matrix: [[Int]]) -> Int {\n        // Get dimensions of the matrix\n        let n = matrix.count    // number of rows\n        let m = matrix[0].count // number of columns\n        \n        // Create a DP table with same dimensions as matrix\n        var dp = Array(repeating: Array(repeating: 0, count: m), count: n)\n        \n        // Variable to store total count of squares\n        var ans = 0\n        \n        // Initialize first column of DP table\n        for i in 0..<n {\n            dp[i][0] = matrix[i][0]\n            ans += dp[i][0]  // Add the count of squares from the first column\n        }\n        \n        // Initialize first row of DP table\n        for j in 1..<m {\n            dp[0][j] = matrix[0][j]\n            ans += dp[0][j]  // Add the count of squares from the first row\n        }\n        \n        // Fill the DP table for remaining cells\n        for i in 1..<n {\n            for j in 1..<m {\n                // Only process if current cell in matrix is 1\n                if matrix[i][j] == 1 {\n                    // For each cell, check the minimum value among:\n                    // 1. Left cell (dp[i][j-1])\n                    // 2. Top cell (dp[i-1][j])\n                    // 3. Top-left diagonal cell (dp[i-1][j-1])\n                    // Add 1 to this minimum value\n                    dp[i][j] = 1 + min(dp[i][j-1], dp[i-1][j], dp[i-1][j-1])\n                }\n                // Add current cell\'s value to total count\n                ans += dp[i][j]\n            }\n        }\n        \n        // Return total count of squares\n        return ans\n    }\n}\n```\n```javascript [JS]\n// JavaScript\n\n\n/**\n * @param {number[][]} matrix\n * @return {number}\n */\nfunction countSquares(matrix) {\n    // Get dimensions of the matrix\n    const n = matrix.length;    // number of rows\n    const m = matrix[0].length; // number of columns\n    \n    // Create a DP table with same dimensions as matrix\n    const dp = Array(n).fill().map(() => Array(m).fill(0));\n    \n    // Variable to store total count of squares\n    let ans = 0;\n    \n    // Initialize first column of DP table\n    for (let i = 0; i < n; i++) {\n        dp[i][0] = matrix[i][0];\n        ans += dp[i][0];\n    }\n    \n    // Initialize first row of DP table\n    for (let j = 1; j < m; j++) {\n        dp[0][j] = matrix[0][j];\n        ans += dp[0][j];\n    }\n    \n    // Fill the DP table for remaining cells\n    for (let i = 1; i < n; i++) {\n        for (let j = 1; j < m; j++) {\n            if (matrix[i][j] === 1) {\n                dp[i][j] = 1 + Math.min(\n                    dp[i][j-1],\n                    dp[i-1][j],\n                    dp[i-1][j-1]\n                );\n            }\n            ans += dp[i][j];\n        }\n    }\n    \n    return ans;\n}\n```\n```typescript [TS]\n// TypeScript\n\n\nfunction countSquares(matrix: number[][]): number {\n    const n: number = matrix.length;    // number of rows\n    const m: number = matrix[0].length; // number of columns\n    \n    // Create a DP table with same dimensions as matrix\n    const dp: number[][] = Array(n).fill(0).map(() => Array(m).fill(0));\n    \n    let ans: number = 0;\n    \n    // Initialize first column of DP table\n    for (let i = 0; i < n; i++) {\n        dp[i][0] = matrix[i][0];\n        ans += dp[i][0];\n    }\n    \n    // Initialize first row of DP table\n    for (let j = 1; j < m; j++) {\n        dp[0][j] = matrix[0][j];\n        ans += dp[0][j];\n    }\n    \n    // Fill the DP table for remaining cells\n    for (let i = 1; i < n; i++) {\n        for (let j = 1; j < m; j++) {\n            if (matrix[i][j] === 1) {\n                dp[i][j] = 1 + Math.min(\n                    dp[i][j-1],\n                    dp[i-1][j],\n                    dp[i-1][j-1]\n                );\n            }\n            ans += dp[i][j];\n        }\n    }\n    \n    return ans;\n}\n```\n```rust []\nimpl Solution {\n    pub fn count_squares(matrix: Vec<Vec<i32>>) -> i32 {\n        let n = matrix.len();\n        let m = matrix[0].len();\n        \n        // Create DP table\n        let mut dp = vec![vec![0; m]; n];\n        let mut ans = 0;\n        \n        // Initialize first column\n        for i in 0..n {\n            dp[i][0] = matrix[i][0];\n            ans += dp[i][0];\n        }\n        \n        // Initialize first row\n        for j in 1..m {\n            dp[0][j] = matrix[0][j];\n            ans += dp[0][j];\n        }\n        \n        // Fill the DP table\n        for i in 1..n {\n            for j in 1..m {\n                if matrix[i][j] == 1 {\n                    dp[i][j] = 1 + dp[i][j-1].min(dp[i-1][j]).min(dp[i-1][j-1]);\n                }\n                ans += dp[i][j];\n            }\n        }\n        \n        ans\n    }\n}\n```\n```ruby []\ndef count_squares(matrix)\n    # Get dimensions of the matrix\n    n = matrix.size        # number of rows\n    m = matrix[0].size     # number of columns\n    \n    # Create a DP table with same dimensions as matrix\n    dp = Array.new(n) { Array.new(m, 0) }\n    \n    # Variable to store total count of squares\n    ans = 0\n    \n    # Initialize first column of DP table\n    n.times do |i|\n        dp[i][0] = matrix[i][0]\n        ans += dp[i][0]\n    end\n    \n    # Initialize first row of DP table\n    (1...m).each do |j|\n        dp[0][j] = matrix[0][j]\n        ans += dp[0][j]\n    end\n    \n    # Fill the DP table for remaining cells\n    (1...n).each do |i|\n        (1...m).each do |j|\n            if matrix[i][j] == 1\n                dp[i][j] = 1 + [dp[i][j-1], dp[i-1][j], dp[i-1][j-1]].min\n            end\n            ans += dp[i][j]\n        end\n    end\n    \n    ans\nend\n```\n![image.png](https://assets.leetcode.com/users/images/9dc1b265-b175-4bf4-bc6c-4b188cb79220_1728176037.4402142.png)\n\n\n### Complexity \n- Time complexity: O(n * m)\n\n- Space complexity: O(n * m)\n\n\n\n## Explanation Step by Step\n\n---\n1. Purpose of the Algorithm\n- This code counts the total number of square submatrices that contain only 1\'s in a given binary matrix.\n2. Initialization Steps\n```\n// Matrix dimensions\nint n = matrix.size();    // rows\nint m = matrix[0].size(); // columns\n// Create DP table\nvector<vector<int>> dp(n, vector<int>(m, 0));\nint ans = 0;\n\n```\n\n3. Base Cases Setup\n- First column initialization:\n```\nfor (int i = 0; i < n; i++) {\n    dp[i][0] = matrix[i][0];\n    ans += dp[i][0];\n}\n\n```\n\n- First row initialization:\n```\nfor (int j = 1; j < m; j++) {\n    dp[0][j] = matrix[0][j];\n    ans += dp[0][j];\n}\n\n```\n4. Main DP Logic\n- For each cell (i,j), if matrix[i][j] = 1:\n    - Look at three adjacent cells: left, top, and diagonal top-left\n    - Take minimum of these three values and add 1\n    - This gives the size of the largest square possible at current position\n```\ndp[i][j] = 1 + min({dp[i][j-1], dp[i-1][j], dp[i-1][j-1]});\n\n```\n\n5. Why This Works\n- dp[i][j] represents the size of the largest square submatrix ending at position (i,j)\n- If any of the three adjacent positions has a smaller value, we can\'t form a larger square\n- Adding 1 accounts for the current cell itself\n\n6. Example For matrix:\n```\n1 1 1\n1 1 1\n1 1 1\n\n```\nThe DP table becomes:\n\n```\n1 1 1\n1 2 2\n1 2 3\n```\n\nWhere each number represents the size of the largest square possible at that position.\n\n7. Final Answer\n- The sum of all values in the DP table gives the total count of all possible squares\n- Each value in dp[i][j] contributes to that many squares ending at position (i,j)\n\n---\n\n![image.png](https://assets.leetcode.com/users/images/2596346d-ea64-4815-a5b6-3cf148c755ba_1729988348.8825893.png)\n![image.png](https://assets.leetcode.com/users/images/d336879c-b962-4e27-8289-7a08dcfb5fc2_1729989278.125466.png)\n\n\n\n
['Swift', 'C++', 'Java', 'Go', 'TypeScript', 'Python3', 'Rust', 'Ruby', 'JavaScript', 'C#']