DSA sheet · Arrays · Prefix Sum pattern

Matrix Block Sum (2D Prefix Sum)

This video takes the prefix sum idea we know from 1D arrays and stretches it to a 2D grid (a matrix). The teacher says the question is easy with brute force, but most people get lost when they try to speed it up with a 2D prefix sum. So she does not hand us a formula to memorise. She derives both formulas herself: one to build the prefix matrix, and one to read the sum of any rectangle out of it. Once you can derive them, you can rebuild them in an interview from any corner you like.

The same 2D prefix sum is the core of many other problems (LeetCode 304 "Range Sum Query 2D", counting sub-matrices, image filters), so this is a page worth knowing very well.

Every part below follows the same order:
① the question in simple words → ② what the constraints tell us → ③ intuition → ④ building the logic from examples → ⑤ approach steps → ⑥ code → ⑦ code line by line → ⑧ dry run → ⑨ complexity & remember

• Part 0 · What you must know before starting (1D prefix, suffix, 2D prefix)
• Part A · Brute force: add up every window cell by cell
• Part B · Optimal: 2D prefix sum matrix
• Part C · Revision page

Part 0 · Before starting

The four array patterns, and why this one is prefix sum

The teacher reminds us of the four patterns she keeps coming back to for arrays: two pointers, sliding window, prefix sum and Kadane's algorithm. For this problem only prefix sum fits. The reason: we are asked for the sum of a range again and again, and many of those ranges overlap. That "same additions repeated many times" smell is the signal for prefix sum.

What is a prefix sum? (1D)

Take an array. The prefix of position i means "everything from index 0 up to and including index i". The prefix sum prefix[i] is the total of that piece.

How each box is built, one by one:

• prefix[0] = nums[0] = 1. Nothing comes before index 0, so it is just the first number (the base case).
• prefix[1] = prefix[0] + nums[1] = 1 + 2 = 3
• prefix[2] = prefix[1] + nums[2] = 3 + 3 = 6
• prefix[3] = 6 + 4 = 10, prefix[4] = 10 + 5 = 15

Rule: prefix[i] = prefix[i-1] + nums[i]. We never re-add the old numbers. The box on the left already holds their total.

Why bother? Many queries

If someone asks for the sum of one range, a simple loop is fine. But the teacher's point is about many queries: "sum from here to here, now from there to there, …". With q queries and a loop of up to n steps each, that is q × n work. With a prefix array built once in O(n), each query is answered in O(1), a single subtraction.

The range formula: sum(l..r) = prefix[r] − prefix[l−1]

Say the query is l = 2, r = 3 (the numbers 3 and 4, total 7).

prefix[3] covers indexes 0..3. We only want 2..3, so the extra piece is 0..1, and its total sits in prefix[1], which is prefix[l-1]. So the answer is 10 − 3 = 7 ✓.

The "−1" problem and the "empty prefix = 0" trick

If l = 0, the formula asks for prefix[-1], which is out of the array. (In Python, [-1] even silently gives you the last element, which is wrong here.) The teacher gives two fixes:

1. Handle index 0 as a separate base case and start the loop from index 1 (and treat "l = 0" specially in queries).
2. Add one extra box at the front holding 0. That box means "the sum of nothing", the empty prefix. Now everything shifts right by one: pre[i+1] = sum of nums[0..i], and the range formula becomes pre[r+1] − pre[l], which never goes out of range.

We will use exactly this padding trick in 2D: an extra row of zeros on top and an extra column of zeros on the left.

def build_prefix(nums):
    pre = [0] * (len(nums) + 1)          # pre[0] = 0, the empty prefix
    for i in range(len(nums)):
        pre[i + 1] = pre[i] + nums[i]    # shifted by one
    return pre

def range_sum(pre, l, r):                # sum of nums[l..r], both included
    return pre[r + 1] - pre[l]

Why always from index 0? The suffix version

The teacher asks a good question: why do we always add up from the start? We could add up from the end instead. That is called a suffix sum: suffix[i] = total of everything from index i to the last index.

Both arrays reach the same grand total (15), just at opposite ends. Both can answer range queries. Only the formula changes:

• Prefix: the bigger value is at the right end, so sum(l..r) = prefix[r] − prefix[l−1].
• Suffix: the bigger value is at the left end, so sum(l..r) = suffix[l] − suffix[r+1]. For l = 2, r = 3: 12 − 5 = 7 ✓. Doing "right minus left" here would give a negative number.

Why she shows this: in a matrix you can start adding from any of the four corners, and each choice gives a different (but equally valid) formula. Seeing it in 1D first makes the 2D case less scary.

What a 2D prefix sum stores

A matrix has rows (horizontal lines, numbered top to bottom from 0) and columns (vertical lines, numbered left to right from 0). Cell (r, c) is row r, column c. We will pick the top-left corner (0, 0) as our anchor. Then each prefix cell stores the sum of the whole rectangle from (0, 0) down to that cell.

  matrix            what "prefix at (1, 2)" covers
  1  2  3           [1  2  3]
  4  5  6           [4  5  6]   = 1+2+3+4+5+6 = 21
  7  8  9            7  8  9

We could also anchor at the top-right, bottom-left or bottom-right corner. Each gives its own formulas. The teacher sticks to top-left in this video and leaves the others as practice (the bottom-right version is solved in Part C).

Part A · Brute force: add up every window

LeetCode 1314 · Matrix Block Sum

1The question in simple words

You get an m × n matrix mat (m rows, n columns) and a number k. Build an answer matrix of the same size. For every cell (i, j), the answer is the sum of all cells within distance k of it in both directions:

• rows from i − k to i + k, and
• columns from j − k to j + k,
• counting only cells that really exist inside the matrix (a valid position).

Picture a square "window" of size (2k+1) × (2k+1) centred on the cell. The answer is the sum of whatever part of the window lies inside the matrix.

       c0 c1 c2
  r0 [  1  2  3 ]
  r1 [  4  5  6 ]
  r2 [  7  8  9 ]

  [ 12 21 16 ]
  [ 27 45 33 ]
  [ 24 39 28 ]

The teacher explains two cells of this example:

  [ 1  2  3 ]
  [ 4 (5) 6 ]
  [ 7  8  9 ]
  sum = 45

   x   x   x
   x [(1)  2] 3
   x [ 4   5] 6
       7   8  9
  only 4 real cells: 1+2+4+5 = 12

• For the centre (1,1) with k = 1: rows 0..2 and columns 0..2, which is the whole matrix → 1+2+…+9 = 45.
• For the corner (0,0): rows −1..1, columns −1..1. The window has 9 spots, but the 5 marked x are outside the matrix, so we skip them. Only 1, 2, 4, 5 count → 12.

LeetCode's second example: same matrix, k = 2. Now every window covers the whole 3 × 3 matrix, so every answer cell is 45.

2What the constraints tell us

• 1 <= m, n, k <= 100 → the matrix is never empty (at least 1 × 1), so no empty-input base case. And k can be as big as the matrix, even bigger than it, so windows can stick out on every side. We must handle out-of-range cells.
• 1 <= mat[i][j] <= 100 → small positive values. The biggest possible sum is 100 × 100 × 100 = 10⁶, a normal int is enough.
• The teacher says she will come back to the constraints when deciding whether we need to optimise. We do that in step 9: the brute force reaches about 10⁸ operations, which is the TLE danger zone.

3Intuition: how would you do it by hand?

Stand on a cell. Put a (2k+1) × (2k+1) stencil centred on it. Walk over every spot of the stencil. If the spot is inside the matrix, add its number. If it's outside, ignore it. Write the total in the answer matrix at the same position. Then move to the next cell and do it all again.

Two loops pick the cell (i, j). Two more loops walk the stencil (r, c). So it's four nested loops.

4Building the logic from examples

How big is the window? 2k + 1

With k = 1, rows go from i − 1 to i + 1: that's 3 rows. In general, from i − k to i + k there are k rows above, k rows below and the row itself: 2k + 1 rows. Same for columns. So the window has (2k+1) × (2k+1) spots: 3 × 3 = 9 when k = 1.

Walking the window for cell (0, 0), k = 1

The row loop goes from i − k = −1 to i + k = 1. The column loop goes from j − k = −1 to j + k = 1. Both ends are included, so in Python the range end is i + k + 1. The column loop runs fully for each row, so the order is: row −1 left to right, then row 0, then row 1.

Notice we still visit all 9 spots, even the 5 invalid ones. We just don't add them.

The "is it valid?" check

A position (r, c) exists only when all four of these hold:

• r >= 0 (not above the top row) and r < m where m = len(mat) = the number of rows (not below the last row),
• c >= 0 (not left of the first column) and c < n where n = len(mat[0]) = the length of the first row = the number of columns.

Only then do we do total += mat[r][c].

Where does the total go?

After the two inner loops finish, total is the block sum for the cell we were standing on, so it goes into ans[i][j]. That's why we need the two outer loops over i (0..m−1) and j (0..n−1): they decide which cell we're standing on, and remember where to write. total must be reset to 0 for each new cell.

The waste the teacher points out

For cell (0,0) we added 1, 2, 4, 5. For cell (1,1) we add all 9 numbers, including 1, 2, 4, 5 again. We already knew their total (12), yet we add them from scratch. Neighbouring windows overlap a lot, and brute force recomputes the overlap every single time. That repeated work is exactly what we remove in Part B.

5Approach steps

1. m = number of rows, n = number of columns. Make an m × n answer matrix of zeros.
2. For every cell (i, j): set total = 0.
3. Loop r from i − k to i + k, and inside it c from j − k to j + k (both ends included).
4. If (r, c) is inside the matrix, add mat[r][c] to total.
5. Store total in ans[i][j].
6. Return ans.

6Code (Python)

class Solution:
    def matrixBlockSum(self, mat, k):
        m, n = len(mat), len(mat[0])            # rows, columns
        ans = [[0] * n for _ in range(m)]       # same size as mat

        for i in range(m):                      # pick the centre cell
            for j in range(n):
                total = 0
                for r in range(i - k, i + k + 1):       # rows of the window
                    for c in range(j - k, j + k + 1):   # columns of the window
                        if 0 <= r < m and 0 <= c < n:  # skip spots outside
                            total += mat[r][c]
                ans[i][j] = total
        return ans

7Code line by line

8Dry run

Matrix 1..9, k = 1. We already did cell (0,0) spot by spot in step 4 (answer 12). Here is every cell, showing which part of the window is real:

Result: [[12,21,16],[27,45,33],[24,39,28]] ✓. Each of the 9 cells tried 9 spots: 81 visits for a 3 × 3 matrix. Count how many times the number 5 was added: 9 times (it's inside every window). That's the waste.

9Complexity & remember

• The two outer loops visit every cell: m × n.
• For each cell, the two inner loops run (2k+1) × (2k+1) times, even when most spots are outside.
• Time O(m · n · (2k+1)²). Expanding, (2k+1)² = 4k² + 4k + 1, and the biggest part is 4k², so this is about O(m · n · k²).
• The constraints let m, n and k all be 100. If we treat them as one size, that's like size⁴ = (10²)⁴ = 10⁸. Counting exactly: 100 · 100 · 201 · 201 ≈ 4 × 10⁸. That is right at (or past) the ~10⁸ TLE limit.
• On LeetCode it did get accepted, but it beat only about 5% of submissions: very slow. So we optimise.
• Space O(1) extra, apart from the answer matrix we must return.

Part B · Optimal: 2D prefix sum

1The question (same as Part A)

Same input and output. What changes is how we get each block sum: instead of adding (2k+1)² numbers, we will read it from a precomputed table with one formula, in O(1).

2What the constraints tell us now

• Brute force is ~10⁸ (step 9 above), so we need something about m × n instead.
• m, n ≥ 1 → the prefix matrix is at least 2 × 2 with the padding. Fine.
• k can be larger than the matrix → the window must be clamped to the matrix edges (explained below).

3Intuition: precompute once, then subtract

In 1D, the prefix array lets us get any range sum by subtraction. A block (rectangle) in a matrix is just a "2D range". So we will build a prefix matrix where each cell holds the sum of the rectangle from the top-left corner (0,0) to that cell. Then any rectangle's sum can be cut out of the big corner rectangles with a few additions and subtractions.

That gives two jobs, and the teacher derives a formula for each:

1. Build the prefix matrix (formula 1).
2. Query it for each cell's window (formula 2).

4Building the logic from examples

4a. Why the prefix matrix gets one extra row and one extra column

Remember the 1D "−1" problem. In 2D we will look at i − 1 and j − 1, which can fall off the top or the left edge. The teacher's two options are the same as in 1D:

• fill the first row and first column as base cases, then start from (1,1), or
• add one extra row of zeros on top and one extra column of zeros on the left, so the prefix matrix is (m+1) × (n+1).

She uses the second option. The zeros mean "empty rectangle, sum 0". The price: everything shifts by one. Cell (i, j) of mat lives at (i+1, j+1) in prefix. Or, the other way round, prefix[i][j] belongs to mat[i−1][j−1].

  mat (3×3)            prefix (4×4), zero row/column added
                          0   0   0   0
   1  2  3                0   ?   ?   ?
   4  5  6       →        0   ?   ?   ?
   7  8  9                0   ?   ?   ?
  prefix[i][j] = sum of mat from (0,0) to (i-1, j-1)

4b. Formula 1: building prefix[i][j] (the four rectangles)

We fill the prefix matrix row by row, left to right. So when we reach prefix[i][j], the cell above it, the cell to its left, and the cell diagonally up-left are already done. Here's what each of them covers, drawn on the mat region from (0,0) to our cell (marked *):

 # # #
 # # #
 # # *

 . . .
 . . .
 . . *
 mat[i-1][j-1]

 T T T
 T T T
 . . .
 prefix[i-1][j]

 L L .
 L L .
 L L .
 prefix[i][j-1]

 X X .
 X X .
 . . .
 prefix[i-1][j-1]

Add ① + ② + ③ and count how many times each cell got added:

  2 2 1        ← the X block (top-left) got added twice:
  2 2 1          once inside T, once inside L
  1 1 1        so subtract it once (④) and every cell counts exactly once

The teacher's board example: 2 + 8 + 8 − 5 = 13

On the board she fills one prefix cell using numbers like these. Here's a small grid that gives the same numbers, so you can check it yourself:

  1 1 2
  1 2 1
  1 2 2

  cell itself          = 2
  top  (rows 0-1, all) = 1+1+2+1+2+1 = 8
  left (all, cols 0-1) = 1+1+1+2+1+2 = 8
  overlap (2×2 corner) = 1+1+1+2     = 5

So 2 + 8 + 8 − 5 = 13. She then checks it the slow way by adding every number in the rectangle directly, and gets 13 again ✓. The point: instead of running two loops over the whole rectangle, each prefix cell costs O(1), because it reuses three neighbours.

4c. Building the whole prefix matrix, cell by cell (mat = 1..9)

Row 0 and column 0 of prefix stay 0. Then:

  1  2  3
  4  5  6
  7  8  9

  0   0   0   0
  0   1   3   6
  0   5  12  21
  0  12  27  45

Check one: prefix[2][2] = 12 should be the sum of mat from (0,0) to (1,1) = 1+2+4+5 = 12 ✓. And prefix[3][3] = 45 is the whole matrix ✓.

This prefix matrix is not the answer yet. It's a tool, like the prefix array in 1D. Now we need the second formula to read each window from it.

4d. Which rectangle does cell (i, j) need? Corners r1, c1, r2, c2

The window of cell (i, j) is the rectangle with

• top-left corner (r1, c1) = (i − k, j − k), and
• bottom-right corner (r2, c2) = (i + k, j + k).

A rectangle is fully described by these two corners, so that's all we need.

4e. Clamping the corners at the matrix border

Near an edge, these corners fall outside the matrix. For cell (0,0) with k = 1, the top-left corner is (−1, −1), which doesn't exist. For cell (2,2), the bottom-right corner is (3, 3), past the last row and column. The teacher's fix: pull each corner back to the nearest real cell, called clamping.

  (-1,-1) x   x   x
          x  [1   2]  3
          x  [4   5]  6
              7   8   9
  r1 = max(0, -1) = 0
  c1 = max(0, -1) = 0
  r2 = min(2, 1)  = 1
  c2 = min(2, 1)  = 1

   1   2   3
   4  [5   6]  x
   7  [8   9]  x
       x   x   x (3,3)
  r1 = max(0, 1) = 1
  c1 = max(0, 1) = 1
  r2 = min(2, 3) = 2
  c2 = min(2, 3) = 2

• r1 = max(0, i − k): if i − k is negative, use row 0 instead. Otherwise keep it.
• c1 = max(0, j − k): same for the first column.
• r2 = min(m − 1, i + k): m − 1 is the last row. If i + k goes past it, use the last row.
• c2 = min(n − 1, j + k): n − 1 is the last column.

Clamping is exactly the brute force's "skip spots outside the matrix", done once for the whole rectangle instead of spot by spot.

4f. Shift into prefix coordinates (+1)

r1, c1, r2, c2 are positions in mat. In the prefix matrix everything sits one step down and right, so the teacher adds 1 to all four: r1 += 1, c1 += 1, r2 += 1, c2 += 1. After the shift, the rectangle is rows r1..r2 and columns c1..c2 in prefix numbering.

4g. Formula 2: the sum of the block (the four rectangles)

Now the main derivation. Take a 5 × 5 matrix and a block in the middle (B). We only have corner rectangles that all start at (0,0).

 o o o o .
 o o o o .
 o B B B .
 o B B B .
 . . . . .

 A A A A .
 A A A A .
 o B B B .
 o B B B .
 . . . . .

 L o o o .
 L o o o .
 L B B B .
 L B B B .
 . . . . .

 X o o o .
 X o o o .
 o B B B .
 o B B B .
 . . . . .

• ① prefix[r2][c2] holds everything from (0,0) to the block's bottom-right corner. It contains our block, plus extra stuff above it and to its left.
• ② The strip above the block ends one row before r1, in the same last column c2. Its total sits at prefix[r1-1][c2]. Subtract it.
• ③ The strip to the left ends one column before c1, in the same last row r2. Its total sits at prefix[r2][c1-1]. Subtract it.
• ④ The top-left corner (X) was inside both strips, so we subtracted it twice. It should be removed only once, so add it back once: prefix[r1-1][c1-1].

This is the 2D version of prefix[r] − prefix[l−1]: in 1D we cut off one piece (the left), in 2D we cut off two pieces (above and left) and repair the double cut.

5Approach steps

1. m, n = rows, columns. Make prefix of size (m+1) × (n+1), all zeros.
2. For i from 1 to m and j from 1 to n: prefix[i][j] = mat[i-1][j-1] + prefix[i-1][j] + prefix[i][j-1] - prefix[i-1][j-1].
3. Make ans of size m × n.
4. For every cell (i, j): clamp the corners: r1 = max(0, i-k), c1 = max(0, j-k), r2 = min(m-1, i+k), c2 = min(n-1, j+k).
5. Shift all four by +1 into prefix numbering.
6. ans[i][j] = prefix[r2][c2] - prefix[r1-1][c2] - prefix[r2][c1-1] + prefix[r1-1][c1-1].
7. Return ans.

6Code (Python)

class Solution:
    def matrixBlockSum(self, mat, k):
        m, n = len(mat), len(mat[0])

        # 1) build the prefix matrix, one extra row and column of zeros
        prefix = [[0] * (n + 1) for _ in range(m + 1)]
        for i in range(1, m + 1):
            for j in range(1, n + 1):
                prefix[i][j] = (mat[i - 1][j - 1]       # the cell itself
                                + prefix[i - 1][j]      # top part
                                + prefix[i][j - 1]      # left part
                                - prefix[i - 1][j - 1]) # overlap counted twice

        # 2) answer each cell with one formula
        ans = [[0] * n for _ in range(m)]
        for i in range(m):
            for j in range(n):
                r1 = max(0, i - k)          # top-left corner, clamped
                c1 = max(0, j - k)
                r2 = min(m - 1, i + k)      # bottom-right corner, clamped
                c2 = min(n - 1, j + k)
                r1, c1, r2, c2 = r1 + 1, c1 + 1, r2 + 1, c2 + 1   # into prefix numbering
                ans[i][j] = (prefix[r2][c2]
                             - prefix[r1 - 1][c2]       # strip above
                             - prefix[r2][c1 - 1]       # strip on the left
                             + prefix[r1 - 1][c1 - 1])  # corner removed twice
        return ans

7Code line by line

8Dry run: every answer cell (mat = 1..9, k = 1)

The prefix matrix from step 4c, for reference:

  prefix     col0 col1 col2 col3
  row0          0    0    0    0
  row1          0    1    3    6
  row2          0    5   12   21
  row3          0   12   27   45

For each cell: clamp in mat numbering, shift +1, then apply formula 2 = big − above − left + corner.

Answer: [[12,21,16],[27,45,33],[24,39,28]] ✓, the same as brute force.

Cell (2,2) as a story: all four rectangles in action

1. Window rows 1..3, cols 1..3. Clamp: r2 = min(2, 3) = 2, c2 = min(2, 3) = 2. So the block is rows 1..2, cols 1..2 → the numbers 5, 6, 8, 9.
2. Shift: r1 = 2, c1 = 2, r2 = 3, c2 = 3.
3. Big: prefix[3][3] = 45, the whole matrix.
4. Above: prefix[1][3] = 6, which is row 0 (1+2+3). Subtract → 39.
5. Left: prefix[3][1] = 12, which is column 0 (1+4+7). Subtract → 27.
6. But the 1 at (0,0) was in both strips, so it was removed twice. Corner: prefix[1][1] = 1. Add it back → 28.
7. Check: 5 + 6 + 8 + 9 = 28 ✓.

Cells touching the top or left edge get 0 for "above" / "left" / "corner": those terms land on the padding row or column. The padding does the edge handling for free.

9Complexity & remember

• Building the prefix: two loops over m × n, O(1) work each → m·n.
• Filling the answer: two loops over m × n, O(1) work each → m·n.
• Time: 2·m·n = O(m·n), at most 2 × 10⁴ steps. The teacher's comparison: about size² instead of size⁴. k no longer matters at all. A huge window costs the same as a tiny one.
• Space O(m·n) for the prefix matrix (plus the answer we return).
• She submitted it and it passed, far faster than brute force.

Part C · Revision page

Practice: the teacher's homework, anchor at the bottom-right corner

She challenges us to build the prefix from a different corner and re-derive both formulas. Here's the bottom-right version. S[i][j] = sum of the rectangle from (i, j) down to the bottom-right corner. The padding now goes on the bottom and right, and since S[i][j] matches mat[i][j] directly, no shift is needed.

• Build (go from the bottom-right backwards): cell + the part below + the part on the right − their overlap (down-right): S[i][j] = mat[i][j] + S[i+1][j] + S[i][j+1] - S[i+1][j+1].
• Query: big rectangle starts at the block's top-left now: S[r1][c1] - S[r2+1][c1] - S[r1][c2+1] + S[r2+1][c2+1]. (Remove the strip below, the strip to the right, add back the corner removed twice.)

class Solution:
    def matrixBlockSum(self, mat, k):
        m, n = len(mat), len(mat[0])
        S = [[0] * (n + 1) for _ in range(m + 1)]   # zero row at bottom, zero column at right
        for i in range(m - 1, -1, -1):
            for j in range(n - 1, -1, -1):
                S[i][j] = mat[i][j] + S[i + 1][j] + S[i][j + 1] - S[i + 1][j + 1]

        ans = [[0] * n for _ in range(m)]
        for i in range(m):
            for j in range(n):
                r1, c1 = max(0, i - k), max(0, j - k)
                r2, c2 = min(m - 1, i + k), min(n - 1, j + k)
                ans[i][j] = S[r1][c1] - S[r2 + 1][c1] - S[r1][c2 + 1] + S[r2 + 1][c2 + 1]
        return ans

s = Solution()
print(s.matrixBlockSum([[1,2,3],[4,5,6],[7,8,9]], 1))   # [[12,21,16],[27,45,33],[24,39,28]]
print(s.matrixBlockSum([[1,2,3],[4,5,6],[7,8,9]], 2))   # [[45,45,45],[45,45,45],[45,45,45]]
print(s.matrixBlockSum([[7]], 3))                       # [[7]]
print(s.matrixBlockSum([[1,2,3,4]], 1))                 # [[3,6,9,7]]
print(s.matrixBlockSum([[1],[2],[3]], 1))               # [[3],[6],[5]]

Based on this video: Matrix Block Sum | Running Sum of 2D Array | Prefix Sum