Range Sum Query 2D - Immutable

Problem Statement

In this task, you're given a 2D integer matrix and need to design a class, NumMatrix, capable of handling multiple queries to calculate the sum of a submatrix. The submatrix is defined by two corners: an upper left corner (row1, col1) and a lower right corner (row2, col2). Each query must return the sum of the matrix values within these bounds efficiently.

Key functionalities to implement in the NumMatrix class include:

• NumMatrix(int[][] matrix) – Initializes the object with the entire matrix, setting up any required pre-computed structures to answer the sum queries efficiently.
• int sumRegion(int row1, int col1, int row2, int col2) – After initialization, this method should efficiently compute and return the sum of the submatrix defined by the corners.

Examples

Example 1

Input:

["NumMatrix", "sumRegion", "sumRegion", "sumRegion"]
[[[[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]]], [2, 1, 4, 3], [1, 1, 2, 2], [1, 2, 2, 4]]

Output:

[null, 8, 11, 12]

Explanation:

NumMatrix numMatrix = new NumMatrix([
  [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]
]);

numMatrix.sumRegion(2, 1, 4, 3); // return 8
numMatrix.sumRegion(1, 1, 2, 2); // return 11
numMatrix.sumRegion(1, 2, 2, 4); // return 12

Constraints

• m == matrix.length
• n == matrix[i].length
• 1 <= m, n <= 200
• -10⁴ <= matrix[i][j] <= 10⁴
• 0 <= row1 <= row2 < m
• 0 <= col1 <= col2 < n
• At most 10⁴ calls will be made to sumRegion.

Approach and Intuition

To meet the constraint of answering each sumRegion query in O(1) time, we precompute a 2D prefix sum matrix during initialization.

1. Build the Prefix Sum Matrix

Let prefixSum[i][j] be the sum of all values in the submatrix from (0, 0) to (i, j) inclusive. Compute it using:

prefixSum[i][j] = matrix[i][j]
                + (i > 0 ? prefixSum[i-1][j] : 0)
                + (j > 0 ? prefixSum[i][j-1] : 0)
                - (i > 0 && j > 0 ? prefixSum[i-1][j-1] : 0)

This equation adds the current cell’s value, the row and column contributions, and removes the overlapping region.

2. Answering a sumRegion Query

To get the sum of a submatrix from (row1, col1) to (row2, col2), use:

sumRegion(row1, col1, row2, col2) = prefixSum[row2][col2]
                                 - (row1 > 0 ? prefixSum[row1-1][col2] : 0)
                                 - (col1 > 0 ? prefixSum[row2][col1-1] : 0)
                                 + (row1 > 0 && col1 > 0 ? prefixSum[row1-1][col1-1] : 0)

This subtracts the areas above and to the left of the desired submatrix and re-adds the overlapping top-left corner that was subtracted twice.

Summary

• Initialization: O(m × n) – builds the prefix sum matrix.
• Each sumRegion call: O(1) – constant-time lookup using precomputed values.
• Space Complexity: O(m × n) – additional memory for the prefix sum matrix.

This ensures maximum efficiency even with a high number of sum queries.

Solutions

class MatrixSumQuery {
    private int[][] sumMatrix;
    
    public MatrixSumQuery(int[][] matrix) {
        if (matrix.length == 0 || matrix[0].length == 0) return;
        sumMatrix = new int[matrix.length + 1][matrix[0].length + 1];
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[0].length; j++) {
                sumMatrix[i + 1][j + 1] = sumMatrix[i + 1][j] + sumMatrix[i][j + 1] + matrix[i][j] - sumMatrix[i][j];
            }
        }
    }
    
    public int computeSum(int r1, int c1, int r2, int c2) {
        return sumMatrix[r2 + 1][c2 + 1] - sumMatrix[r1][c2 + 1] - sumMatrix[r2 + 1][c1] + sumMatrix[r1][c1];
    }
}