Leetcode - Count Square Submatrices with All Ones
https://leetcode.com/problems/count-square-submatrices-with-all-ones/
Given a m * n
matrix of ones and zeros, return how many square submatrices have all ones.
Example 1:
Input: matrix = [ [0,1,1,1], [1,1,1,1], [0,1,1,1] ] Output: 15 Explanation: There are 10 squares of side 1. There are 4 squares of side 2. There is 1 square of side 3. Total number of squares = 10 + 4 + 1 = 15.
func countSquares(matrix [][]int) int { m := len(matrix) n := len(matrix[0]) dp := make([][]int, m+1) for i := 0; i < len(dp); i++ { dp[i] = make([]int, n+1) } result := 0 for i := 0; i < m; i++ { for j := 0; j < n; j++ { if matrix[i][j] == 1 { dp[i+1][j+1] = min(dp[i][j], dp[i+1][j], dp[i][j+1]) + 1 } result += dp[i+1][j+1] } } return result } func min(nums ...int) int { num := nums[0] for _, n := range nums { if num > n { num = n } } return num }
time complexity: O(m*n)
space complexity: O(m*n)