Skip to content

Latest commit

 

History

History
70 lines (64 loc) · 2.62 KB

1314. Matrix Block Sum.md

File metadata and controls

70 lines (64 loc) · 2.62 KB

1314. Matrix Block Sum

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]]

Solution

  • java

    • mine Runtime: 3 ms, faster than 95.07%, Memory Usage: 41.7 MB, less than 100.00% of Java online submissions

      public int[][] matrixBlockSum(int[][] mat, int K) {
    int m = mat.length;
    int n = mat[0].length;
    int[][] temp = new int[m + 1][n + 1];
    for(int i = 0; i < m; i++){
        for(int j = 0; j < n; j++){
            temp[i + 1][j + 1] = temp[i+1][j] + temp[i][j+1] - temp[i][j] + mat[i][j];
        }
    }
    int[][] res = new int[m][n];
     for(int i = 0; i < m; i++){
        for(int j = 0; j < n; j++){
            int r1 = Math.max(0, i - K);
            int c1 = Math.max(0, j - K);
            int r2 = Math.min(m, i + K + 1);
            int c2 = Math.min(n, j + K + 1);
            res[i][j] =temp[r2][c2] - temp[r2][c1] - temp[r1][c2] + temp[r1][c1];
        }
    }
    return res;
}

    • the most votes Runtime: 3 ms, faster than 95.07%, Memory Usage: 41.7 MB, less than 100.00% of Java online submissions

      public int[][] matrixBlockSum(int[][] mat, int K) {
    int m = mat.length, n = mat[0].length;
    int[][] rangeSum = new int[m + 1][n + 1];
    for (int i = 0; i < m; ++i)
        for (int j = 0; j < n; ++j)
            rangeSum[i + 1][j + 1] = rangeSum[i + 1][j] + rangeSum[i][j + 1] - rangeSum[i][j] + mat[i][j];
    int[][] ans = new int[m][n];
    for (int i = 0; i < m; ++i)
        for (int j = 0; j < n; ++j) {
            int r1 = Math.max(0, i - K), c1 = Math.max(0, j - K), r2 = Math.min(m, i + K + 1), c2 = Math.min(n, j + K + 1);
            ans[i][j] = rangeSum[r2][c2] - rangeSum[r2][c1] - rangeSum[r1][c2] + rangeSum[r1][c1];
        }
    return ans;
}

Explaination