Description
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.
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]Solution in Python
To solve the problem where sumRegion must work in O(1) time complexity, we can use a prefix sum technique. By precomputing the sum of all elements from the top-left corner of the matrix to each position, we can then compute the sum of any submatrix in constant time.
Approach
- Precompute Prefix Sum: We will create a 2D array
prefixSumwhereprefixSum[i][j]contains the sum of the rectangle from the top-left corner(0, 0)to(i, j). - Prefix Sum Calculation:
- For each element
matrix[i][j], the sum from the top-left corner to that point can be computed as: prefixSum[i][j]=matrix[i][j]+prefixSum[i−1][j]+prefixSum[i][j−1]−prefixSum[i−1][j−1] - We subtract
prefixSum[i-1][j-1]because it gets added twice.
- For each element
- Querying the Submatrix Sum:
- Once the prefix sum is precomputed, the sum of any submatrix from
(row1, col1)to(row2, col2)can be calculated as: Sum=prefixSum[row2][col2]−prefixSum[row1−1][col2]−prefixSum[row2][col1−1]+prefixSum[row1−1][col1−1] - This formula ensures that the overlap between the top and left is not subtracted twice.
- Once the prefix sum is precomputed, the sum of any submatrix from
Python
from typing import List
class NumMatrix:
def __init__(self, matrix: List[List[int]]):
# Initialize the matrix dimensions
self.rows = len(matrix)
self.cols = len(matrix[0]) if self.rows > 0 else 0
# Create a prefix sum matrix with one extra row and column for ease of computation
self.prefixSum = [[0] * (self.cols + 1) for _ in range(self.rows + 1)]
# Populate the prefix sum matrix
for i in range(1, self.rows + 1):
for j in range(1, self.cols + 1):
# Compute the prefix sum for each element
self.prefixSum[i][j] = (matrix[i-1][j-1]
+ self.prefixSum[i-1][j] # sum above
+ self.prefixSum[i][j-1] # sum on the left
- self.prefixSum[i-1][j-1]) # remove overlap
def sumRegion(self, row1: int, col1: int, row2: int, col2: int) -> int:
# Adjust indices to match the 1-based prefix sum array
row1 += 1
col1 += 1
row2 += 1
col2 += 1
# Calculate the sum of the desired submatrix using the prefix sums
return (self.prefixSum[row2][col2]
- self.prefixSum[row1-1][col2]
- self.prefixSum[row2][col1-1]
+ self.prefixSum[row1-1][col1-1])
Explanation of the Code
- Initialization (
__init__):- We calculate the dimensions of the input matrix.
- A 2D prefix sum matrix
prefixSumis initialized with an extra row and column (to handle boundary cases easily). - We iterate over the matrix and compute the prefix sum for each element using the previously described formula.
- Querying (
sumRegion):- The query adjusts the given
row1, col1, row2, col2indices to match the 1-based index system of theprefixSummatrix. - It computes the sum of the submatrix using the precomputed
prefixSumvalues with the formula.
- The query adjusts the given
Solution in C++
C++
#include <vector>
using namespace std;
class NumMatrix {
public:
// 2D vector to store the prefix sums
vector<vector<int>> prefixSum;
// Constructor: Initializes the prefixSum matrix using the input matrix
NumMatrix(vector<vector<int>>& matrix) {
int rows = matrix.size();
int cols = matrix[0].size();
// Create a 2D prefix sum array with an extra row and column (initialized to 0)
prefixSum = vector<vector<int>>(rows + 1, vector<int>(cols + 1, 0));
// Compute the prefix sums for every element in the matrix
for (int i = 1; i <= rows; ++i) {
for (int j = 1; j <= cols; ++j) {
// prefixSum[i][j] is the sum of all elements from (0,0) to (i-1, j-1) in the original matrix
// Use the inclusion-exclusion principle:
prefixSum[i][j] = matrix[i-1][j-1] // Current element from the matrix
+ prefixSum[i-1][j] // Sum of the row above
+ prefixSum[i][j-1] // Sum of the column to the left
- prefixSum[i-1][j-1]; // Remove the overlap (top-left diagonal)
}
}
}
// Function to calculate the sum of the submatrix from (row1, col1) to (row2, col2)
int sumRegion(int row1, int col1, int row2, int col2) {
// Adjust indices to work with the 1-based prefix sum array
row1++; col1++; row2++; col2++;
// Use the prefix sums to calculate the sum of the region
return prefixSum[row2][col2] // Total sum up to (row2, col2)
- prefixSum[row1-1][col2] // Exclude the area above the top row
- prefixSum[row2][col1-1] // Exclude the area left of the leftmost column
+ prefixSum[row1-1][col1-1]; // Add back the overlap area (which was subtracted twice)
}
};Solution in Javascript
JavaScript
var NumMatrix = function(matrix) {
// Get the number of rows and columns
const rows = matrix.length;
const cols = matrix[0].length;
// Initialize the prefixSum matrix with an extra row and column
this.prefixSum = Array.from({ length: rows + 1 }, () => Array(cols + 1).fill(0));
// Compute the prefix sums for every element in the matrix
for (let i = 1; i <= rows; i++) {
for (let j = 1; j <= cols; j++) {
// Use inclusion-exclusion principle to compute the prefix sum
this.prefixSum[i][j] = matrix[i - 1][j - 1]
+ this.prefixSum[i - 1][j] // Sum from the row above
+ this.prefixSum[i][j - 1] // Sum from the column to the left
- this.prefixSum[i - 1][j - 1]; // Remove overlap from top-left
}
}
};
/**
* @param {number} row1
* @param {number} col1
* @param {number} row2
* @param {number} col2
* @return {number}
*/
NumMatrix.prototype.sumRegion = function(row1, col1, row2, col2) {
// Adjust indices to match the 1-based prefixSum array
row1++;
col1++;
row2++;
col2++;
// Calculate the sum of the submatrix using the prefix sum array
return this.prefixSum[row2][col2]
- this.prefixSum[row1 - 1][col2] // Subtract the region above the top row
- this.prefixSum[row2][col1 - 1] // Subtract the region left of the leftmost column
+ this.prefixSum[row1 - 1][col1 - 1]; // Add back the overlap that was subtracted twice
};Solution in Java
Java
class NumMatrix {
// 2D array to store the prefix sums
private int[][] prefixSum;
// Constructor: Initializes the prefixSum matrix using the input matrix
public NumMatrix(int[][] matrix) {
int rows = matrix.length;
int cols = matrix[0].length;
// Initialize the prefixSum matrix with an extra row and column (all values initialized to 0)
prefixSum = new int[rows + 1][cols + 1];
// Compute the prefix sums for every element in the matrix
for (int i = 1; i <= rows; i++) {
for (int j = 1; j <= cols; j++) {
// Use inclusion-exclusion principle to compute the prefix sum
prefixSum[i][j] = matrix[i - 1][j - 1]
+ prefixSum[i - 1][j] // Sum of the row above
+ prefixSum[i][j - 1] // Sum of the column to the left
- prefixSum[i - 1][j - 1]; // Remove the overlap from the top-left
}
}
}
// Method to calculate the sum of the submatrix from (row1, col1) to (row2, col2)
public int sumRegion(int row1, int col1, int row2, int col2) {
// Adjust the indices to match the 1-based indexing of the prefixSum array
row1++;
col1++;
row2++;
col2++;
// Use the precomputed prefix sums to calculate the sum of the submatrix
return prefixSum[row2][col2]
- prefixSum[row1 - 1][col2] // Subtract the area above the top row
- prefixSum[row2][col1 - 1] // Subtract the area left of the leftmost column
+ prefixSum[row1 - 1][col1 - 1]; // Add back the overlap area that was subtracted twice
}
}