[Golang & Python] Dynamic Programming | Simple Approach - Beat 100% | O(mn) Time & O(1) Space
\n\n# Approach\n- We make the first iteration through the matrix, calculating the maximum size of submatrices which the current cell can get\n- If the cell is e
![image.png](https://assets.leetcode.com/users/images/92b278c6-019b-4bb8-9ca9-c62e35575377_1730012074.4255939.png)\n\n# Approach\n- We make the first iteration through the matrix, calculating the maximum size of submatrices which the current cell can get\n- If the cell is empty, we can skip it\n- Else, the current cell is the bottom right corner of a submatrix. We can calculate its size by getting the minimum size of its top left direction cells: `[row-1][col-1]` (top-left), `[row-1][col]` (top) and `[row][col-1]` (left) plus `1`\n- Make the second iteration and combine all the updated maximum submatrix sizes for the result `ans`\n\n# Complexity\n- Time complexity: `O(mn)` (traverse the matrix two times)\n\n- Space complexity: `O(1)` (directly update the matrix)\n\n# Code\n```golang []\nfunc countSquares(matrix [][]int) int {\n    // Step 1: Traverse through the matrix\n    // If the cell is empty, we skip it\n    // Else, the current cell is the bottom right corner of a submatrix with its size\n    // equals to minimum size of top, left and top-left cells plus 1\n    for row := 1; row < len(matrix); row++ {\n        for col := 1; col < len(matrix[0]); col++ {\n            if matrix[row][col] == 0 {\n                continue\n            }\n            matrix[row][col] = min(matrix[row-1][col-1], min(matrix[row-1][col], matrix[row][col-1])) + 1\n        }\n    }\n\n    // Step 2: Traverse the matrix again,\n    // combine the updated maximum sizes of every cell\n    ans := 0\n    for row := 0; row < len(matrix); row++ {\n        for col := 0; col < len(matrix[0]); col++ {\n            ans += matrix[row][col]\n        }\n    }\n    return ans\n}\n```\n```python []\nclass Solution(object):\n    def countSquares(self, matrix):\n        # Step 1: Traverse through the matrix\n        # If the cell is empty, we skip it\n        # Else, the current cell is the bottom right corner of a submatrix with its size\n        # equals to minimum size of up, left and up-left cells plus 1\n        for row in range(1, len(matrix)):\n            for col in range(1, len(matrix[0])):\n                if matrix[row][col] == 0:\n                    continue\n                matrix[row][col] = min(matrix[row-1][col-1], matrix[row-1][col], matrix[row][col-1]) + 1\n        \n        # Step 2: Traverse the matrix again,\n        # combine the updated maximum sizes of every cell\n        ans = 0\n        for row in matrix:\n            for cell in row:\n                ans += cell\n        return ans\n```\n
['Dynamic Programming', 'Matrix', 'Python', 'Go']