Skip to content
Hello Python

Answer Matrix Region Sums

Practice ExerciseIntermediateMedium2D Prefix SumArrayMatrix / Grid

Checking your account…

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

Loading the interactive Practice workspace.If it does not appear, the problem and learning material remain readable, but browser execution is unavailable.Reload Practice workspace

Problem

Implement matrix_region_sums(matrix, queries). Each query is [top, left, bottom, right] with inclusive indexes. Return one sum per query. matrix is non-empty and rectangular.

Starter code

def matrix_region_sums(matrix, queries):
    pass
Test cases

mixed-regions

{
  "args": [
    [
      [
        1,
        2,
        3
      ],
      [
        4,
        5,
        6
      ]
    ],
    [
      [
        0,
        0,
        0,
        2
      ],
      [
        0,
        1,
        1,
        2
      ],
      [
        1,
        1,
        1,
        2
      ]
    ]
  ]
}

Expected: [6,16,11]

single-cell

{
  "args": [
    [
      [
        5,
        1
      ],
      [
        2,
        7
      ]
    ],
    [
      [
        1,
        1,
        1,
        1
      ]
    ]
  ]
}

Expected: [7]

Wizard outline
  1. Step 1: Accumulate one row

    Answer full-height-one row ranges. A running row sum establishes the horizontal prefix component.

  2. Step 2: Accumulate across rows

    Build a complete two-dimensional prefix table. Adding the prefix above each row prefix represents every rectangle from the origin.

  3. Step 3: Exclude outside bands

    Answer arbitrary inclusive rectangles. Subtracting the top and left bands removes outside cells, while adding their overlap back corrects double subtraction.

Footguns and prerequisites
  • Adding the overlapping prefix twice double-counts the upper-left region.
  • Unpadded tables create fragile negative-index boundary branches.
  • arrays strings two pointers sliding window
Reviewed references
Recommended approach and implementation

Build a padded origin-prefix table, then apply four-corner inclusion-exclusion for every query.

Why it works: 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.

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