medium

Range Sum Query 2D - Immutable

Answer repeated queries for the sum of values inside a rectangle of a fixed grid.

1. Define the problem

Range Sum Query 2D - Immutable

Given a fixed 2D matrix, answer repeated queries for the sum of the values inside the rectangle from (row1, col1) to (row2, col2), inclusive. Build a 2D prefix sum once, where prefixr[c] holds the sum of every cell above and to the left of (r, c). Any rectangle sum is then four lookups and three subtractions — inclusion-exclusion on the corners of the rectangle.

Constraints

  • m == matrix.length
  • n == matrixi.length
  • 1 ≤ m, n ≤ 200
  • -105 ≤ matrixi[j] ≤ 105
  • 0 ≤ row1 ≤ row2 < m
  • 0 ≤ col1 ≤ col2 < n

Example

Inputmatrix = [[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]], row1=2, col1=1, row2=4, col2=3
Output8

Explanation The values inside that rectangle (2 0 1 / 1 0 1 / 0 3 0) sum to 8.

2. Know the words first

In plain terms

Inclusion-exclusion
Adding back a region that got subtracted twice — here, the top-left corner gets removed by both the row-above cut and the column-left cut, so it has to be added back once.
3. Visualize the solution

Build a 2D prefix grid, then subtract two strips and add back the corner

Build a 2D prefix grid, then subtract two strips and add back the corner
Statusbuild · nothing computed yet

The row is the prefix grid for a 2 x 3 matrix: six cells, one per matrix value. All of them start empty.

What happens in this step

matrix = [[3, 0, 1],
          [5, 6, 3]]

prefix cell "r,c" = the sum of the first r rows and first c columns of matrix.

So "1,1" covers just matrix[0][0], and "2,3" covers the whole matrix.
Anything with a 0 in its label (a row above the top, or a column left of
the edge) is 0 and never needs storing on screen.
Step 1 of 5

Steps to visualize

  1. The walkthrough uses a smaller matrix than the example above, [[3, 0, 1], [5, 6, 3]], so the whole prefix grid fits on one line.
  2. The row is that prefix grid, read left to right, top row first. Cell "r,c" holds the sum of every matrix value above and to the left of it — the first r rows and the first c columns. — means not computed yet.
  3. Build each cell with prefixr[c] = matrix[r-1][c-1] + prefix[r-1][c] + prefixr[c-1] - prefix[r-1][c-1]. Any prefix cell with a 0 in its label is 0, which is why the code keeps a padding row and column.
  4. To query a rectangle, take the prefix cell at its bottom-right, subtract the strip above it and the strip to its left, then add back the top-left corner that both strips removed.
4. Walk through the code

Walk through the code

Same walkthrough, now with the code. Press Next to move one step and watch which lines run.

Build a 2D prefix grid, then subtract two strips and add back the corner
Statusbuild · nothing computed yet

The row is the prefix grid for a 2 x 3 matrix: six cells, one per matrix value. All of them start empty.

What happens in this step

matrix = [[3, 0, 1],
          [5, 6, 3]]

prefix cell "r,c" = the sum of the first r rows and first c columns of matrix.

So "1,1" covers just matrix[0][0], and "2,3" covers the whole matrix.
Anything with a 0 in its label (a row above the top, or a column left of
the edge) is 0 and never needs storing on screen.
Step 1 of 5
5. Solution

Solution

solution.tsTypeScript
function sumRegion(matrix, row1, col1, row2, col2) {
  const rows = matrix.length;
  const cols = matrix[0].length;
  const prefix = Array.from({ length: rows + 1 }, () => new Array(cols + 1).fill(0));

  for (let r = 0; r < rows; r++) {
    for (let c = 0; c < cols; c++) {
      prefix[r + 1][c + 1] = matrix[r][c] + prefix[r][c + 1] + prefix[r + 1][c] - prefix[r][c];
    }
  }

  return (
    prefix[row2 + 1][col2 + 1] - prefix[row1][col2 + 1] - prefix[row2 + 1][col1] + prefix[row1][col1]
  );
}
Time
O(rows × cols) to build, O(1) per query
Space
O(rows × cols)
6. Test cases

Test cases

InputExpectedCovers
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]], row1=2, col1=1, row2=4, col2=38example from the docstring
same matrix, row1=1, col1=1, row2=2, col2=211a second region on the same precomputed prefix grid
matrix = [[5]], row1=0, col1=0, row2=0, col2=05smallest valid input, a 1x1 matrix
matrix = [[1,2,3,4]], row1=0, col1=1, row2=0, col2=39a matrix with only one row
matrix = [[1],[2],[3]], row1=0, col1=0, row2=2, col2=06a matrix with only one column
matrix = [[-1,2],[3,-4]], row1=0, col1=0, row2=1, col2=10negative values inside the queried region

Keep reading