1314

1314. Matrix Block Sum (Medium)

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

Related Topics:
Dynamic Programming

Solution 1.

// OJ: https://leetcode.com/problems/matrix-block-sum/
// Author: github.com/lzl124631x
// Time: O(MN)
// Space: O(1)
class Solution {
public:
    vector<vector<int>> matrixBlockSum(vector<vector<int>>& A, int K) {
        int M = A.size(), N = A[0].size();
        for (int i = 0; i < M; ++i) {
            int sum = 0;
            for (int j = 0; j < N; ++j) {
                sum += A[i][j];
                A[i][j] = sum + (i - 1 >= 0 ? A[i - 1][j] : 0);
            }
        }
        vector<vector<int>> ans(M, vector<int>(N));
        for (int i = 0; i < M; ++i) {
            for (int j = 0; j < N; ++j) {
                int minr = max(-1, i - K - 1), maxr = min(M - 1, i + K), minc = max(-1, j - K - 1), maxc = min(N - 1, j + K);
                int a = A[maxr][maxc], b = minc == -1 ? 0 : A[maxr][minc], c = minr == -1 ? 0 : A[minr][maxc], d = minr == -1 || minc == -1 ? 0 : A[minr][minc];
                ans[i][j] = a - b - c + d;
            }
        }
        return ans;
    }
};