LeetCode 1314: Matrix Block Sum Solution

Master LeetCode problem 1314 (Matrix Block Sum), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

1314. Matrix Block Sum

Medium

Array Matrix Prefix Sum

Problem Explanation

Explanation

To solve this problem, we can use the concept of prefix sum. We will first create a prefix sum matrix where each cell stores the sum of all elements to its top left. Then, we can calculate the sum of elements in the required range using the prefix sum matrix efficiently.

Algorithm:

Create a prefix sum matrix by adding the sum of all elements to the top left of each cell.
Iterate over each cell in the given matrix and calculate the sum of elements within the range [i-k, j-k] to [i+k, j+k] using the prefix sum matrix.

Time Complexity: O(mn) where m and n are the dimensions of the matrix. Space Complexity: O(mn) for the prefix sum matrix.

Solution Code

class Solution {
    public int[][] matrixBlockSum(int[][] mat, int k) {
        int m = mat.length;
        int n = mat[0].length;
        int[][] prefixSum = new int[m+1][n+1];
        
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                prefixSum[i][j] = mat[i-1][j-1] + prefixSum[i-1][j] + prefixSum[i][j-1] - prefixSum[i-1][j-1];
            }
        }
        
        int[][] result = 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);
                
                result[i][j] = prefixSum[r2][c2] - prefixSum[r2][c1] - prefixSum[r1][c2] + prefixSum[r1][c1];
            }
        }
        
        return result;
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 1314 (Matrix Block Sum)?

This page provides optimized solutions for LeetCode problem 1314 (Matrix Block Sum) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 1314 (Matrix Block Sum)?

The time complexity for LeetCode 1314 (Matrix Block Sum) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 1314 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 1314 in Java, C++, or Python.

Back to LeetCode Solutions