Formatted question description: https://leetcode.ca/all/1314.html

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.

class Solution {
    public int[][] matrixBlockSum(int[][] mat, int K) {
        int rows = mat.length, columns = mat[0].length;
        int[][] sums = new int[rows][columns];
        for (int i = 0; i < rows; i++) {
            int minRow = Math.max(i - K, 0);
            int maxRow = Math.min(i + K, rows - 1);
            for (int j = 0; j < columns; j++) {
                int minColumn = Math.max(j - K, 0);
                int maxColumn = Math.min(j + K, columns - 1);
                for (int r = minRow; r <= maxRow; r++) {
                    for (int c = minColumn; c <= maxColumn; c++)
                        sums[i][j] += mat[r][c];
                }
            }
        }
        return sums;
    }
}

############

class Solution {
    private int[][] pre;
    private int m;
    private int n;
    public int[][] matrixBlockSum(int[][] mat, int k) {
        int m = mat.length, n = mat[0].length;
        int[][] pre = new int[m + 1][n + 1];
        for (int i = 1; i < m + 1; ++i) {
            for (int j = 1; j < n + 1; ++j) {
                pre[i][j] = pre[i - 1][j] + pre[i][j - 1] + -pre[i - 1][j - 1] + mat[i - 1][j - 1];
            }
        }
        this.pre = pre;
        this.m = m;
        this.n = n;
        int[][] ans = new int[m][n];
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                ans[i][j] = get(i + k + 1, j + k + 1) - get(i + k + 1, j - k)
                    - get(i - k, j + k + 1) + get(i - k, j - k);
            }
        }
        return ans;
    }

    private int get(int i, int j) {
        i = Math.max(Math.min(m, i), 0);
        j = Math.max(Math.min(n, j), 0);
        return pre[i][j];
    }
}

// OJ: https://leetcode.com/problems/matrix-block-sum/
// 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;
    }
};

class Solution:
    def matrixBlockSum(self, mat: List[List[int]], k: int) -> List[List[int]]:
        m, n = len(mat), len(mat[0])
        pre = [[0] * (n + 1) for _ in range(m + 1)]
        for i in range(1, m + 1):
            for j in range(1, n + 1):
                pre[i][j] = (
                    pre[i - 1][j]
                    + pre[i][j - 1]
                    - pre[i - 1][j - 1]
                    + mat[i - 1][j - 1]
                )

        def get(i, j):
            i = max(min(m, i), 0)
            j = max(min(n, j), 0)
            return pre[i][j]

        ans = [[0] * n for _ in range(m)]
        for i in range(m):
            for j in range(n):
                ans[i][j] = (
                    get(i + k + 1, j + k + 1)
                    - get(i + k + 1, j - k)
                    - get(i - k, j + k + 1)
                    + get(i - k, j - k)
                )
        return ans

func matrixBlockSum(mat [][]int, k int) [][]int {
	m, n := len(mat), len(mat[0])
	pre := make([][]int, m+1)
	for i := 0; i < m+1; i++ {
		pre[i] = make([]int, n+1)
	}
	for i := 1; i < m+1; i++ {
		for j := 1; j < n+1; j++ {
			pre[i][j] = pre[i-1][j] + pre[i][j-1] + -pre[i-1][j-1] + mat[i-1][j-1]
		}
	}

	get := func(i, j int) int {
		i = max(min(m, i), 0)
		j = max(min(n, j), 0)
		return pre[i][j]
	}

	ans := make([][]int, m)
	for i := 0; i < m; i++ {
		ans[i] = make([]int, n)
		for j := 0; j < n; j++ {
			ans[i][j] = get(i+k+1, j+k+1) - get(i+k+1, j-k) - get(i-k, j+k+1) + get(i-k, j-k)
		}
	}
	return ans
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

1314 - Matrix Block Sum

1314. Matrix Block Sum (Medium)

Solution 1.

All Problems

All Solutions

Welcome to Subscribe On Youtube

1314. Matrix Block Sum (Medium)

Solution 1.

All Problems

All Solutions