
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 tosumRegion
.
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
- Java
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];
}
}
This Java solution addresses the problem of efficiently querying the sum of subregions within a 2D matrix. The class MatrixSumQuery
uses an advanced data structure to preprocess the input matrix to allow fast sum queries.
At initialization (
MatrixSumQuery
constructor):- Check if the input matrix is non-empty.
- Create an auxiliary matrix,
sumMatrix
, with dimensions larger by one in both directions compared to the input matrix. This extra room facilitates easier calculation of subregion sums, particularly on the borders. - Populate
sumMatrix
using a dynamic programming approach. Each entry atsumMatrix[i + 1][j + 1]
is calculated to store the sum of elements from the top-left corner (0,0) to the current element (i,j) in the original matrix. The formular used issumMatrix[i + 1][j + 1] = sumMatrix[i + 1][j] + sumMatrix[i][j + 1] + matrix[i][j] - sumMatrix[i][j]
.
To compute the sum of any sub-matrix from
(r1, c1)
to(r2, c2)
:- Apply the precomputed results in
sumMatrix
observing the inclusion-exclusion principle. The formula used here,sumMatrix[r2 + 1][c2 + 1] - sumMatrix[r1][c2 + 1] - sumMatrix[r2 + 1][c1] + sumMatrix[r1][c1]
, specifically accounts for area overlaps and right, bottom exclusions due to the initial adjustment in matrix size.
- Apply the precomputed results in
This compact solution ensures that after the O(n*m)
preprocessing time, where n
and m
are the dimensions of the matrix, any sum query can be answered in constant time O(1)
making it highly efficient for scenarios with many sum queries to the same matrix.
No comments yet.