Skip to content
Hello Python
Pattern1 Practice5 Interview

2D Prefix Sum

Use cumulative matrix regions and inclusion-exclusion to answer rectangular range queries. Learn its decision rule, maintained state, Python cost model, and transfer from a focused drill to a full Interview Problem.

Recognize it when

Consider 2D Prefix Sum when the prompt's constraints and required operations match this shape: Use cumulative matrix regions and inclusion-exclusion to answer rectangular range queries.

Pybit demonstrates the 2D Prefix Sum decision pattern in a professional coding interview workspace.
On this page · Store Every Rectangle from the Origin

Checking your account…

Sign in to save your code and progress across devices. The lesson and problem statement remain public.

2D Prefix Sum Code Labs

Store Every Rectangle from the Origin

A 2D prefix cell stores the sum of the rectangle from the matrix origin up to, but not including, its padded row and column boundaries.

Pad Row and Column Zero

Adding a zero row and column makes every original cell map to prefix row plus one and column plus one. Edge rectangles then use the same formula as interior rectangles.

Build a Padded 2D Prefix Grid

Reference
def prefix_grid(matrix):
    if not matrix:return [[0]]
    rows,cols=len(matrix),len(matrix[0]);prefix=[[0]*(cols+1) for _ in range(rows+1)]
    for row in range(rows):
        for col in range(cols):prefix[row+1][col+1]=matrix[row][col]+prefix[row][col+1]+prefix[row+1][col]-prefix[row][col]
    return prefix
Practice

Implement prefix_grid(matrix). Return a rows+1 by cols+1 grid where each cell stores the rectangle sum above and left.

Public tests

  • Use inclusion exclusion while building

Loading interactive editor.If it does not appear, the reference and starter code remain readable.Reload editor

Use Inclusion Exclusion for Queries

For a half-open query, take the large bottom-right prefix, subtract the strip above and the strip left, then add their doubly subtracted overlap. This answers immutable rectangle sums in O(1).

Answer Rectangle Sum Queries

Reference
def rectangle_sums(matrix,queries):
    if not matrix:return []
    rows,cols=len(matrix),len(matrix[0]);prefix=[[0]*(cols+1) for _ in range(rows+1)]
    for r in range(rows):
        for c in range(cols):prefix[r+1][c+1]=matrix[r][c]+prefix[r][c+1]+prefix[r+1][c]-prefix[r][c]
    return [prefix[b][right]-prefix[t][right]-prefix[b][left]+prefix[t][left] for t,left,b,right in queries]
Practice

Implement rectangle_sums(matrix,queries). Queries are half-open [top,left,bottom,right]; return each rectangle sum.

Public tests

  • Cancel outside strips and restore overlap

Loading interactive editor.If it does not appear, the reference and starter code remain readable.Reload editor

Choose 2D Prefixes or Row Prefixes

Choose full 2D prefixes for many arbitrary rectangle queries at O(rows × cols) storage. Choose per-row prefixes when query height is small or memory pressure matters, trading each query for O(height).

Explain It in an Interview

Say: “Each prefix cell owns the origin rectangle. Query inclusion-exclusion subtracts two outside strips and restores their overlap.” Draw the four corners, state half-open boundaries, and count O(RC + Q) total time.

Python Version Note

Python 3.11+

The examples use the standard Python syntax and containers supported by the browser Judge; the 2D Prefix Sum invariant is independent of a minor Python release.

Verify in Python docs(opens in a new tab)

Complexity & Invariants

Interview bounds depend on the stated representation, input model, and real Python operations.

OperationAverageWorstInterview note
2D Prefix Sum decision loopO(rc + q)O(rc + q)Build a padded origin-prefix table, then apply four-corner inclusion-exclusion for every query.

Space

O(rc) for the focused Answer Matrix Region Sums implementation.

Assumptions

  • Each prefix cell stores exactly the origin rectangle above and left of it. The query formula removes the two outside bands and restores their overlap, leaving exactly the requested rectangle.
  • The bound includes real Python operations; no repeated slicing, linear list membership, or hidden sorting is treated as free.

Invariants Worth Saying Aloud

  1. State the precise 2D Prefix Sum invariant before coding and preserve it after every update, traversal step, or recursive return.
  2. prefix[r][c] summarizes rows before r and columns before c.
  3. The doubly counted overlap is added back exactly once.
  4. Build a padded inclusion-exclusion prefix table. Preserve this property after every transition.
  5. Answer each inclusive rectangle from four prefix entries. Preserve this property after every transition.

When To Use Or Avoid 2D Prefix Sum

Use It When

  • Use 2D Prefix Sum when the prompt exposes the ordering, monotonicity, recurrence, or constraint that makes this decision safe.
  • Use it when prefix[r][c] summarizes rows before r and columns before c.

Choose Another Tool When

  • Avoid 2D Prefix Sum when its decision rule cannot eliminate work or preserve the required state.
  • Avoid forcing the label onto a prompt whose simpler direct scan already meets the constraints.

Common Pitfalls

These are the mistakes most likely to survive a happy-path example and fail a boundary case.

Moving state without a proof

Applying the pattern without proving its ordering, monotonicity, or window invariant can silently miss valid candidates.

Prevent it: Write the decision rule beside the loop and verify it against Answer Matrix Region Sums before optimizing.

Avoid

def matrix_region_sums(matrix, queries):
    pass

Use instead

def matrix_region_sums(matrix, queries):
    rows, cols = len(matrix), len(matrix[0])
    prefix = [[0] * (cols + 1) for _ in range(rows + 1)]
    for row in range(rows):
        running = 0
        for col in range(cols):
            running += matrix[row][col]
            prefix[row + 1][col + 1] = running + prefix[row][col + 1]
    results = []
    for top, left, bottom, right in queries:
        results.append(prefix[bottom + 1][right + 1] - prefix[top][right + 1] - prefix[bottom + 1][left] + prefix[top][left])
    return results

Where you will hit this: Answer Matrix Region Sums(opens in a new tab)

Breaking the maintained state

Subtracts both outside bands without restoring their overlap.

Prevent it: Use the public tests and preserve this state: prefix[r][c] summarizes rows before r and columns before c.

Avoid

def matrix_region_sums(matrix, queries):
    p=[[0]*(len(matrix[0])+1) for _ in range(len(matrix)+1)]
    for r,row in enumerate(matrix):
        for c,v in enumerate(row): p[r+1][c+1]=v+p[r][c+1]+p[r+1][c]-p[r][c]
    return [p[b+1][d+1]-p[a][d+1]-p[b+1][l] for a,l,b,d in queries]

Use instead

def matrix_region_sums(matrix, queries):
    rows, cols = len(matrix), len(matrix[0])
    prefix = [[0] * (cols + 1) for _ in range(rows + 1)]
    for row in range(rows):
        running = 0
        for col in range(cols):
            running += matrix[row][col]
            prefix[row + 1][col + 1] = running + prefix[row][col + 1]
    results = []
    for top, left, bottom, right in queries:
        results.append(prefix[bottom + 1][right + 1] - prefix[top][right + 1] - prefix[bottom + 1][left] + prefix[top][left])
    return results

Where you will hit this: Answer Matrix Region Sums(opens in a new tab)

Hiding Python work in the hot path

Python slicing, copying, membership in lists, or repeated sorting inside the loop can invalidate the intended complexity.

Prevent it: Count every slice, copy, sort, membership check, and container update before claiming O(rc + q).

Avoid

def matrix_region_sums(matrix, queries):
    p=[[0]*(len(matrix[0])+1) for _ in range(len(matrix)+1)]
    for r,row in enumerate(matrix):
        for c,v in enumerate(row): p[r+1][c+1]=v+p[r][c+1]+p[r+1][c]-p[r][c]
    return [p[b+1][d+1]-p[a][d+1]-p[b+1][l] for a,l,b,d in queries]

Use instead

def matrix_region_sums(matrix, queries):
    rows, cols = len(matrix), len(matrix[0])
    prefix = [[0] * (cols + 1) for _ in range(rows + 1)]
    for row in range(rows):
        running = 0
        for col in range(cols):
            running += matrix[row][col]
            prefix[row + 1][col + 1] = running + prefix[row][col + 1]
    results = []
    for top, left, bottom, right in queries:
        results.append(prefix[bottom + 1][right + 1] - prefix[top][right + 1] - prefix[bottom + 1][left] + prefix[top][left])
    return results

Where you will hit this: Binary Subarrays With Sum(opens in a new tab)

Reviewed References

Official Python documentation supports language behavior. Canonical problem pages provide additional practice context.