Range Sum Query 2D - Immutable
MedPrompt
Given a 2D matrix matrix, handle multiple queries of the following type:
- Calculate the sum of the elements of
matrixinside the rectangle defined by its upper left corner(row1, col1)and lower right corner(row2, col2).
Implement the NumMatrix class:
NumMatrix(int[][] matrix)Initializes the object with the integer matrixmatrix.int sumRegion(int row1, int col1, int row2, int col2)Returns the sum of the elements ofmatrixinside the rectangle defined by its upper left corner(row1, col1)and lower right corner(row2, col2).
You must design an algorithm where sumRegion works on O(1) time complexity.
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 (i.e sum of the red rectangle)
numMatrix.sumRegion(1, 1, 2, 2); // return 11 (i.e sum of the green rectangle)
numMatrix.sumRegion(1, 2, 2, 4); // return 12 (i.e sum of the blue rectangle)
Constraints:
m == matrix.lengthn == matrix[i].length1 <= m, n <= 200-104 <= matrix[i][j] <= 1040 <= row1 <= row2 < m0 <= col1 <= col2 < n- At most
104calls will be made tosumRegion.
Approaches
3 approaches with complexity analysis and trade-offs.
The most straightforward approach is to calculate the sum for each query by iterating through all elements in the specified rectangle. For each sumRegion call, we traverse the matrix from (row1, col1) to (row2, col2) and accumulate the sum.
Algorithm
- Store the original matrix in the constructor
- For each
sumRegionquery:- Initialize sum to 0
- Iterate through rows from row1 to row2
- For each row, iterate through columns from col1 to col2
- Add each element to the sum
- Return the accumulated sum
Walkthrough
This approach directly calculates the sum for each query without any preprocessing. When sumRegion(row1, col1, row2, col2) is called, we iterate through all rows from row1 to row2 and all columns from col1 to col2, adding each element to our running sum.
class NumMatrix { private int[][] matrix; public NumMatrix(int[][] matrix) { this.matrix = matrix; } public int sumRegion(int row1, int col1, int row2, int col2) { int sum = 0; for (int i = row1; i <= row2; i++) { for (int j = col1; j <= col2; j++) { sum += matrix[i][j]; } } return sum; }}This approach is simple to implement and understand, but it doesn't meet the O(1) requirement for sumRegion operations.
Complexity
Time
O(1) for constructor, O(m*n) for sumRegion in worst case where m and n are the dimensions of the query rectangle
Space
O(1) additional space (only storing reference to original matrix)
Trade-offs
Pros
Simple and straightforward implementation
No additional space required beyond storing the original matrix
Easy to understand and debug
Cons
Does not meet the O(1) requirement for sumRegion
Inefficient for multiple queries as it recalculates the same sums
Performance degrades significantly with larger query rectangles
This approach preprocesses each row to store cumulative sums, allowing us to calculate the sum of any row segment in O(1) time. For each query, we sum up the contributions from each row in the specified range.
Algorithm
- During initialization:
- Create a 2D prefix sum array with an extra column
- For each row, compute cumulative sums from left to right
- For each
sumRegionquery:- Initialize sum to 0
- For each row from row1 to row2:
- Add the difference between prefix sums at col2+1 and col1
- Return the accumulated sum
Walkthrough
We precompute prefix sums for each row during initialization. For each row, we store cumulative sums from the beginning of the row to each column. When answering a query, we iterate through each row in the range and use the precomputed prefix sums to get the sum of the column range in O(1) time per row.
class NumMatrix { private int[][] prefixSum; public NumMatrix(int[][] matrix) { if (matrix.length == 0 || matrix[0].length == 0) return; int m = matrix.length; int n = matrix[0].length; prefixSum = new int[m][n + 1]; // Extra column for easier calculation for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { prefixSum[i][j + 1] = prefixSum[i][j] + matrix[i][j]; } } } public int sumRegion(int row1, int col1, int row2, int col2) { int sum = 0; for (int i = row1; i <= row2; i++) { sum += prefixSum[i][col2 + 1] - prefixSum[i][col1]; } return sum; }}This approach reduces the time complexity of sumRegion compared to brute force, but still doesn't achieve O(1) as required.
Complexity
Time
O(m*n) for constructor, O(m) for sumRegion where m is the number of rows in the query
Space
O(m*n) for storing the prefix sum array
Trade-offs
Pros
Better than brute force for wide rectangles
Each row sum calculation is O(1)
Relatively simple to implement and understand
Cons
Still doesn't achieve O(1) for sumRegion
Uses additional space proportional to the matrix size
Performance depends on the height of the query rectangle
This approach uses 2D prefix sums to precompute the sum of all rectangles from (0,0) to any point (i,j). Using the inclusion-exclusion principle, we can calculate any rectangle sum in O(1) time by combining four prefix sum values.
Algorithm
- During initialization:
- Create a 2D prefix sum array with extra row and column (filled with zeros)
- For each cell (i,j), compute prefixSum[i][j] = matrix[i-1][j-1] + prefixSum[i-1][j] + prefixSum[i][j-1] - prefixSum[i-1][j-1]
- For each
sumRegionquery:- Apply inclusion-exclusion principle using four corner values from prefix sum array
- Return the result in O(1) time
Walkthrough
We create a 2D prefix sum array where prefixSum[i][j] represents the sum of all elements in the rectangle from (0,0) to (i-1,j-1). To calculate the sum of a rectangle from (row1,col1) to (row2,col2), we use the inclusion-exclusion principle:
sum = prefixSum[row2+1][col2+1] - prefixSum[row1][col2+1] - prefixSum[row2+1][col1] + prefixSum[row1][col1]
class NumMatrix { private int[][] prefixSum; public NumMatrix(int[][] matrix) { if (matrix.length == 0 || matrix[0].length == 0) return; int m = matrix.length; int n = matrix[0].length; prefixSum = new int[m + 1][n + 1]; // Extra row and column for easier calculation for (int i = 1; i <= m; i++) { for (int j = 1; j <= n; j++) { prefixSum[i][j] = matrix[i-1][j-1] + prefixSum[i-1][j] + prefixSum[i][j-1] - prefixSum[i-1][j-1]; } } } public int sumRegion(int row1, int col1, int row2, int col2) { return prefixSum[row2 + 1][col2 + 1] - prefixSum[row1][col2 + 1] - prefixSum[row2 + 1][col1] + prefixSum[row1][col1]; }}This approach achieves the required O(1) time complexity for sumRegion operations by leveraging the mathematical property that any rectangle sum can be computed using four corner values from the prefix sum array.
Complexity
Time
O(m*n) for constructor, O(1) for sumRegion
Space
O(m*n) for storing the 2D prefix sum array
Trade-offs
Pros
Achieves O(1) time complexity for sumRegion as required
Efficient for multiple queries
Mathematically elegant solution using inclusion-exclusion principle
Cons
Requires additional space proportional to matrix size
More complex to implement correctly (easy to make off-by-one errors)
Preprocessing time is proportional to matrix size
Solutions
Solution
class NumMatrix { private int [][] s ; public NumMatrix ( int [][] matrix ) { int m = matrix . length , n = matrix [ 0 ]. length ; s = new int [ m + 1 ][ n + 1 ]; for ( int i = 0 ; i < m ; ++ i ) { for ( int j = 0 ; j < n ; ++ j ) { s [ i + 1 ][ j + 1 ] = s [ i + 1 ][ j ] + s [ i ][ j + 1 ] - s [ i ][ j ] + matrix [ i ][ j ]; } } } public int sumRegion ( int row1 , int col1 , int row2 , int col2 ) { return s [ row2 + 1 ][ col2 + 1 ] - s [ row2 + 1 ][ col1 ] - s [ row1 ][ col2 + 1 ] + s [ row1 ][ col1 ]; } } /** * Your NumMatrix object will be instantiated and called as such: * NumMatrix obj = new NumMatrix(matrix); * int param_1 = obj.sumRegion(row1,col1,row2,col2); *//** * @param {number[][]} matrix */ var NumMatrix = function ( matrix ) { const m = matrix . length ; const n = matrix [ 0 ]. length ; this . s = new Array ( m + 1 ). fill ( 0 ). map (() => new Array ( n + 1 ). fill ( 0 )); for ( let i = 0 ; i < m ; ++ i ) { for ( let j = 0 ; j < n ; ++ j ) { this . s [ i + 1 ][ j + 1 ] = this . s [ i + 1 ][ j ] + this . s [ i ][ j + 1 ] - this . s [ i ][ j ] + matrix [ i ][ j ]; } } }; /** * @param {number} row1 * @param {number} col1 * @param {number} row2 * @param {number} col2 * @return {number} */ NumMatrix . prototype . sumRegion = function ( row1 , col1 , row2 , col2 ) { return ( this . s [ row2 + 1 ][ col2 + 1 ] - this . s [ row2 + 1 ][ col1 ] - this . s [ row1 ][ col2 + 1 ] + this . s [ row1 ][ col1 ] ); }; /** * Your NumMatrix object will be instantiated and called as such: * var obj = new NumMatrix(matrix) * var param_1 = obj.sumRegion(row1,col1,row2,col2) */class NumMatrix { public: vector < vector < int >> s ; NumMatrix ( vector < vector < int >>& matrix ) { int m = matrix . size (), n = matrix [ 0 ]. size (); s . resize ( m + 1 , vector < int > ( n + 1 )); for ( int i = 0 ; i < m ; ++ i ) { for ( int j = 0 ; j < n ; ++ j ) { s [ i + 1 ][ j + 1 ] = s [ i + 1 ][ j ] + s [ i ][ j + 1 ] - s [ i ][ j ] + matrix [ i ][ j ]; } } } int sumRegion ( int row1 , int col1 , int row2 , int col2 ) { return s [ row2 + 1 ][ col2 + 1 ] - s [ row2 + 1 ][ col1 ] - s [ row1 ][ col2 + 1 ] + s [ row1 ][ col1 ]; } }; /** * Your NumMatrix object will be instantiated and called as such: * NumMatrix* obj = new NumMatrix(matrix); * int param_1 = obj->sumRegion(row1,col1,row2,col2); */''' >>> a = [ [1,2,3], [4,5,6] ] >>> b = a.copy() >>> b [[1, 2, 3], [4, 5, 6]] ''' class NumMatrix : def __init__ ( self , matrix : List [ List [ int ]]): m , n = len ( matrix ), len ( matrix [ 0 ]) self . s = [[ 0 ] * ( n + 1 ) for _ in range ( m + 1 )] for i , row in enumerate ( matrix ): for j , v in enumerate ( row ): self . s [ i + 1 ][ j + 1 ] = ( self . s [ i ][ j + 1 ] + self . s [ i + 1 ][ j ] - self . s [ i ][ j ] + v ) def sumRegion ( self , row1 : int , col1 : int , row2 : int , col2 : int ) -> int : return ( self . s [ row2 + 1 ][ col2 + 1 ] - self . s [ row2 + 1 ][ col1 ] - self . s [ row1 ][ col2 + 1 ] + self . s [ row1 ][ col1 ] ) # Your NumMatrix object will be instantiated and called as such: # obj = NumMatrix(matrix) # param_1 = obj.sumRegion(row1,col1,row2,col2) ############ class NumMatrix ( object ): def __init__ ( self , matrix ): """ initialize your data structure here. :type matrix: List[List[int]] """ self . dp = [[ 0 ] * len ( matrix [ 0 ]) for i in range ( 0 , len ( matrix ))] for i in range ( 0 , len ( matrix )): for j in range ( 0 , len ( matrix [ 0 ])): if i == 0 : self . dp [ 0 ][ j ] = self . dp [ 0 ][ j - 1 ] + matrix [ i ][ j ] elif j == 0 : self . dp [ i ][ 0 ] = self . dp [ i - 1 ][ 0 ] + matrix [ i ][ j ] else : self . dp [ i ][ j ] = self . dp [ i - 1 ][ j ] + self . dp [ i ][ j - 1 ] - self . dp [ i - 1 ][ j - 1 ] + matrix [ i ][ j ] def sumRegion ( self , row1 , col1 , row2 , col2 ): """ sum of elements matrix[(row1,col1)..(row2,col2)], inclusive. :type row1: int :type col1: int :type row2: int :type col2: int :rtype: int """ dp = self . dp diagSum = dp [ row1 - 1 ][ col1 - 1 ] totalSum = dp [ row2 ][ col2 ] leftSum = dp [ row2 ][ col1 - 1 ] upSum = dp [ row1 - 1 ][ col2 ] if row1 == 0 : upSum = 0 diagSum = 0 if col1 == 0 : leftSum = 0 diagSum = 0 return totalSum - leftSum - upSum + diagSumVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.