Medium

Range Sum Query 2D - Immutable

LAB

Given matrix and [r1,c1,r2,c2] queries, return each submatrix sum.

EXAMPLES

Example 1

Input
{
  "matrix": [
    [
      3,
      0,
      1,
      4,
      2
    ],
    [
      5,
      6,
      3,
      2,
      1
    ],
    [
      1,
      2,
      0,
      1,
      5
    ],
    [
      4,
      1,
      0,
      1,
      7
    ],
    [
      1,
      0,
      3,
      0,
      5
    ]
  ],
  "queries": [
    [
      2,
      1,
      4,
      3
    ],
    [
      1,
      1,
      2,
      2
    ],
    [
      1,
      2,
      2,
      4
    ]
  ]
}

Output
[
  8,
  11,
  12
]

FUNCTION SHAPE

matrix: intMatrixqueries: intMatrix→intArray

SOLUTION NOTE

2D prefix sum with inclusion-exclusion. Pad with zeros to avoid boundary checks. The formula subtracts left and top portions, then adds back the double-subtracted corner.

Reveal reference solution +

pythonREFERENCE

class NumMatrix:
    def __init__(self, matrix: List[List[int]]):
        m, n = len(matrix), len(matrix[0])
        self.ps = [[0] * (n + 1) for _ in range(m + 1)]

        for i in range(1, m + 1):
            for j in range(1, n + 1):
                self.ps[i][j] = (matrix[i-1][j-1] + self.ps[i-1][j] +
                                 self.ps[i][j-1] - self.ps[i-1][j-1])

    def sumRegion(self, r1: int, c1: int, r2: int, c2: int) -> int:
        r1, c1, r2, c2 = r1+1, c1+1, r2+1, c2+1
        return (self.ps[r2][c2] - self.ps[r2][c1-1] -
                self.ps[r1-1][c2] + self.ps[r1-1][c1-1])

TimeO(mn) init, O(1) query

SpaceO(mn)

Open on LeetCode ↗