✅ Easy Solution with O(1) space complexity | C++, Java, Python | Beats 100% | Beginner Friendly 🚀
\u2705\u2705\u2705 Easy Solution with O(1) space complexity explained with diagram || Beginner Friendly || C++, Java, Python \uD83D\uDE80\uD83D\uDE80\uD83D\uDD2
# ***\u2705\u2705\u2705 Easy Solution with O(1) space complexity explained with diagram || Beginner Friendly || C++, Java, Python \uD83D\uDE80\uD83D\uDE80\uD83D\uDD25\uD83D\uDD25***\n# Intuition\nHere, we utilize a concept similar to prefix sums. Instead of tracking the cumulative sum, we focus on counting the number of square submatrices that can be formed with all ones. For each cell containing a 1, we determine the size of the largest square that can end at that cell by looking at its top, left, and top-left neighbors. By updating the cell with the size of the square it can form, we effectively accumulate the total count of such submatrices throughout the matrix. \n\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n---\n\n\n# Approach\nWe will replace the elements in the matrix with the size of the largest square sub-matrix with all ones that each element is part of (without using any additional space). By updating the original matrix, each cell matrix[i][j] will represent the side length of the largest square ending at that cell, effectively counting all possible squares as we process each element.\n\n- **Edge Cases for Boundary Cells:**\n\n    Cells in the first row or first column can only be part of squares of side 1, as they lack sufficient neighbors to form larger squares. As specified in the example, consider cell (0, 1); it has no cell above, so the top value becomes 0. Since matrix[0][1] is 1, it can only contribute a square of size 1x1.\n\n- **Calculating Square Size for Each Cell:**\n\n    For each cell (i, j) where matrix[i][j] == 1, we calculate the potential square size by looking at:\n        \n    - **top** \u2014 the largest square ending above (matrix[i-1][j]).\n    - **left** \u2014 the largest square ending to the left (matrix[i][j-1]).\n    - **diag** \u2014 the largest square ending diagonally up-left (matrix[i-1][j-1]).\n    \n    \n    We find the minimum of top, left, and diag because all three sides need to be the same length to form a larger square. Adding 1 to this minimum gives the side length of the largest square ending at (i, j).\n\n- **Adding to Count:**\n\n    The value matrix[i][j] after updating gives the number of square submatrices that end at that cell. Accumulating these values across the matrix yields the total count of all squares.\n\n\n## Example Walkthrough \n\n**Processing Cell (0, 1) (Edge Case):**\nAs specified in the example, the cell (0, 1) has no cell above it, making top = 0, left = 0, and diag = 0. Since matrix[0][1] itself is 1, it only forms a square of size 1x1, so we leave it as 1.\n\n![image.png](https://assets.leetcode.com/users/images/87314e38-de65-4625-9453-abf49540a284_1730063058.3306973.png)\n\n**Processing Cell (1, 2) (Addition Case):**\nAt cell (1, 2), top = 1, left = 1, and diag = 1, indicating a potential for a larger square.\nTaking the minimum of top, left, and diag gives 1, so we update matrix[1][2] to 1 + 1 = 2, indicating it is part of a 2x2 square.\n\n![image.png](https://assets.leetcode.com/users/images/fb5a5841-6c2c-4794-b31c-468392aa3cb2_1730062558.6040034.png)\n\n**Processing Cell (2, 3) (Addition Case):**\nFor cell (2, 3), top = 2, left = 1, and diag = 1. The minimum of these values is 1, so we update matrix[2][3] to 1 + 1 = 2, meaning it is part of a 2x2 square.\n\n![image.png](https://assets.leetcode.com/users/images/d0723bbf-d5f0-4973-811b-9594fffa60f7_1730062623.5511587.png)\n\nThe modified matrix will look like this: \n\n![image.png](https://assets.leetcode.com/users/images/f8a63484-1f26-465a-8e3e-66e9e56e8d32_1730063932.4464405.png)\n\nThe total of all elements in this modified matrix is **15**, which represents the total count of all square submatrices with all ones.\n\n\n<!-- Describe your approach to solving the problem. -->\n\n---\n\n\n# Complexity\n- Time complexity:O(nm)\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: O(1)\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n---\n\n\n# Code\n```cpp []\nclass Solution {\npublic:\n    int countSquares(vector<vector<int>>& matrix) {\n        int ret = 0;  // Total count of square submatrices\n        \n        for (int i = 0; i < matrix.size(); i++) {\n            for (int j = 0; j < matrix[0].size(); j++) {\n\n                if (matrix[i][j] == 1) {\n                    // Get the minimum of top, left, and diagonal values (if within bounds)\n                    int top = i == 0 ? 0 : matrix[i - 1][j];\n                    int left = j == 0 ? 0 : matrix[i][j - 1];\n                    int diag = (i == 0 || j == 0) ? 0 : matrix[i - 1][j - 1];\n\n                    // Update cell to represent size of largest square ending at (i, j)\n                    matrix[i][j] += min(min(top, left), diag);\n                    \n                    // Add updated cell value to total count\n                    ret += matrix[i][j];\n                }\n            }\n        }\n        return ret;  // Return total count of squares\n    }\n};\n\n```\n```python []\nclass Solution:\n    def countSquares(self, matrix):\n        ret = 0  # Total count of square submatrices\n        \n        for i in range(len(matrix)):\n            for j in range(len(matrix[0])):\n                if matrix[i][j] == 1:\n                    top = matrix[i-1][j] if i > 0 else 0\n                    left = matrix[i][j-1] if j > 0 else 0\n                    diag = matrix[i-1][j-1] if i > 0 and j > 0 else 0\n\n                    matrix[i][j] += min(top, left, diag)\n                    ret += matrix[i][j]\n        \n        return ret\n\n```\n```java []\nclass Solution {\n    public int countSquares(int[][] matrix) {\n        int ret = 0;  // Total count of square submatrices\n        \n        for (int i = 0; i < matrix.length; i++) {\n            for (int j = 0; j < matrix[0].length; j++) {\n                if (matrix[i][j] == 1) {\n                    int top = (i == 0) ? 0 : matrix[i - 1][j];\n                    int left = (j == 0) ? 0 : matrix[i][j - 1];\n                    int diag = (i == 0 || j == 0) ? 0 : matrix[i - 1][j - 1];\n\n                    matrix[i][j] += Math.min(Math.min(top, left), diag);\n                    ret += matrix[i][j];\n                }\n            }\n        }\n        return ret;\n    }\n}\n\n```\n\n<!--<div style="position: relative; width: 100%; height: 0; padding-top: 75%;">\n    <iframe src="https://leetcode.com/playground/RnYTeDgu/shared" \n            frameBorder="0" \n            style="position: absolute; top: 0; left: 0; width: 100%; height: 100%;">\n    </iframe>\n</div>-->\n\n---\n\n\n\n![image.png](https://assets.leetcode.com/users/images/81c254f0-a048-4af0-b597-435ca62042b0_1730066418.2869568.png)\n\n\n\n\n
['Dynamic Programming', 'Python', 'C++', 'Java']