Welcome to Subscribe On Youtube

1314. Matrix Block Sum

Description

Given a m x 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

Solutions

Dynamic programming - 2D preSum.

  • 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];
        }
    }
    
  • class Solution {
    public:
        vector<vector<int>> matrixBlockSum(vector<vector<int>>& mat, int k) {
            int m = mat.size(), n = mat[0].size();
            vector<vector<int>> pre(m + 1, vector<int>(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];
                }
            }
            vector<vector<int>> ans(m, vector<int>(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, m, n, pre) - get(i + k + 1, j - k, m, n, pre) - get(i - k, j + k + 1, m, n, pre) + get(i - k, j - k, m, n, pre);
                }
            }
            return ans;
        }
    
        int get(int i, int j, int m, int n, vector<vector<int>>& pre) {
            i = max(min(m, i), 0);
            j = max(min(n, j), 0);
            return pre[i][j];
        }
    };
    
  • 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
    }
    
  • function matrixBlockSum(mat: number[][], k: number): number[][] {
        const m: number = mat.length;
        const n: number = mat[0].length;
    
        const s: number[][] = Array.from({ length: m + 1 }, () => Array(n + 1).fill(0));
        for (let i = 0; i < m; i++) {
            for (let j = 0; j < n; j++) {
                s[i + 1][j + 1] = s[i][j + 1] + s[i + 1][j] - s[i][j] + mat[i][j];
            }
        }
    
        const ans: number[][] = Array.from({ length: m }, () => Array(n).fill(0));
        for (let i = 0; i < m; i++) {
            for (let j = 0; j < n; j++) {
                const x1: number = Math.max(i - k, 0);
                const y1: number = Math.max(j - k, 0);
                const x2: number = Math.min(m - 1, i + k);
                const y2: number = Math.min(n - 1, j + k);
                ans[i][j] = s[x2 + 1][y2 + 1] - s[x1][y2 + 1] - s[x2 + 1][y1] + s[x1][y1];
            }
        }
    
        return ans;
    }
    
    

All Problems

All Solutions