LeetCode: Matrix Block Sum

Posted on August 5, 2019July 26, 2020 by braindenny

Matrix Block Sum

Similar Problems:

Given a m * n matrix mat and an integer K, return a matrix answer where each answer[i][j] is the sum of all elements mat[r][c] for i – K <= r <= i + K, j – K <= c <= j + K, and (r, c) is a valid position in the matrix.

Example 1:

Input: mat = [[1,2,3],[4,5,6],[7,8,9]], K = 1
Output: [[12,21,16],[27,45,33],[24,39,28]]

Example 2:

Input: mat = [[1,2,3],[4,5,6],[7,8,9]], K = 2
Output: [[45,45,45],[45,45,45],[45,45,45]]

Constraints:

m == mat.length
n == mat[i].length
1 <= m, n, K <= 100
1 <= mat[i][j] <= 100

Github: code.dennyzhang.com

Credits To: leetcode.com

Leave me comments, if you have better ways to solve.

Solution:

// https://code.dennyzhang.com/matrix-block-sum
// Basic Ideas: dynamic programming
//
//  dp(i, j): sum for rectangle from (0, 0) to (i, j)
//    mat2[i][j] = dp(i+k, j+k) + dp(i-k, j-k) - dp(i-k, j+k) - dp(i+k, j-k)
//
// Complexity: Time O(n*m), Space O(n*m)
func min(x, y int) int {
    if x<y {
        return x
    } else {
        return y
    }
}

func max(x, y int) int {
    if x>y {
        return x
    } else {
        return y
    }
}

func matrixBlockSum(mat [][]int, K int) [][]int {
    dp := make([][]int, len(mat)+1)
    for i, _ := range dp {
        dp[i] = make([]int, len(mat[0])+1)
    }
    for i:=1; i<len(dp); i++ {
        for j:=1; j<len(dp[0]); j++ {
            dp[i][j] = dp[i][j-1]+dp[i-1][j]+mat[i-1][j-1]-dp[i-1][j-1]
        }
    }
    res := make([][]int, len(mat))
    for i, _ := range res {
        res[i] = make([]int, len(mat[0]))
    }
    //
    //  (i1, j1) 
    //
    //         (i, j)
    //
    //                 (i2,j2)                 
    for i, _ := range mat {
        for j, _ := range mat[i] {
            i1 := max(0, i-K)
            i2 := min(i+K, len(mat)-1)
            j1 := max(0, j-K)
            j2 := min(j+K, len(mat[0])-1)
            res[i][j] = dp[i2+1][j2+1] + dp[i1][j1] - dp[i1][j2+1] - dp[i2+1][j1]
        }
    }
    return res
}

Post Views: 0