Prefix Sum — Matrix Block Sum

↗ LeetCode: Matrix Block Sum · Medium · pattern chapter →

Asked atGoogleAmazon

Given matrix mat[m][n] and integer k, return answer[i][j] = sum of all elements mat[r][c] with |r-i| ≤ k and |c-j| ≤ k.

Example 1 — mat=[[1,2,3],[4,5,6],[7,8,9]], k=1 → [[12,21,16],[27,45,33],[24,39,28]]Example 2 — mat=[[1,2,3],[4,5,6],[7,8,9]], k=2 → [[45,45,45],[45,45,45],[45,45,45]]

Constraints — 1 ≤ m, n ≤ 100; 1 ≤ k ≤ 100. Brute recomputes each block in O(k²) — O(m·n·k²) = 10⁴·10² = 10⁶ ops at m=n=100, k=10; blows up at larger k. 2D prefix sum is O(m·n) = 10⁴ ops with O(1) per query.

Progressive Hints

Try to solve it yourself first. Reveal hints only when stuck — each hint is progressively more specific.

---

⏱️Interview timer00:00

Practice under interview pressure. Start when you begin reading; stop when you finish. Save best only when you had a full working solution.

Target for interview: Medium = 20-25 min · Hard = 30-40 min · Best time persists on this device only.

Approach 1 — For each cell, sum k-neighborhood

O(m·n·k²). Baseline.

Approach 2 — 2D prefix sum

Insight. Build pref[i][j] = sum of mat[0..i-1][0..j-1]. Then any rectangle sum = O(1) via inclusion-exclusion.

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

Execution Trace

2D pref — mat=[[1,2,3],[4,5,6],[7,8,9]], k=1

Step 1 / 2cell (0,0) neighborhood sum

Complexity — Time O(m·n); Space O(m·n).

---

Try it yourself

Complexity summary

Approach	Time	Space	Grade
Neighborhood sum	O(m·n·k²)	O(1)	baseline
2D prefix sum	O(m·n)	O(m·n)	optimum

When to use which

• Many rectangle-sum queries on static matrix → 2D prefix sum.
• Updates + queries → 2D Fenwick / BIT.
• 1D version → same technique on a 1D prefix array.

✨AI Study CompanionBeta

Related problems

• Range Sum Query 2D - Immutable — same technique
• Count Submatrices with Target Sum
• Maximal Rectangle

Was this page helpful?