Untitled

class Solution {
    public int[][] matrixBlockSum(int[][] mat, int k) {
        int m = mat.length;
        int n = mat[0].length;

        // Step 1: Build the prefix sum matrix
        int[][] prefixSum = new int[m][n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                prefixSum[i][j] = mat[i][j];
                if (i > 0) prefixSum[i][j] += prefixSum[i - 1][j]; // Add sum from above
                if (j > 0) prefixSum[i][j] += prefixSum[i][j - 1]; // Add sum from left
                if (i > 0 && j > 0) prefixSum[i][j] -= prefixSum[i - 1][j - 1]; // Remove overlap
            }
        }

        // Step 2: Compute the result matrix
        int[][] answer = new int[m][n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                // Determine the bounds of the window
                int r1 = Math.max(0, i - k); // Top row
                int c1 = Math.max(0, j - k); // Left column
                int r2 = Math.min(m - 1, i + k); // Bottom row
                int c2 = Math.min(n - 1, j + k); // Right column

                // Calculate the sum of the window using the prefix sum matrix
                answer[i][j] = prefixSum[r2][c2];
                if (r1 > 0) answer[i][j] -= prefixSum[r1 - 1][c2]; // Subtract top region
                if (c1 > 0) answer[i][j] -= prefixSum[r2][c1 - 1]; // Subtract left region
                if (r1 > 0 && c1 > 0) answer[i][j] += prefixSum[r1 - 1][c1 - 1]; // Add back overlap
            }
        }

        return answer;
    }
}