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)

• 相关文章
• 全局相关文章