304. Range Sum Query 2D - Immutable

Description

The NumMatrix problem requires implementing a class that can efficiently calculate the sum of elements within a submatrix of a given 2D matrix. The class should support multiple queries to sum the elements within any rectangular region defined by its top-left and bottom-right corners.

Intuition

To efficiently calculate the sum of elements within a submatrix, we can leverage a prefix sum technique. Instead of summing the elements in the submatrix directly each time a query is made, we precompute a prefix sum matrix. This matrix allows us to compute the sum of any submatrix in constant time by using the inclusion-exclusion principle.

Approach

1. Prefix Sum Matrix Construction: - Create a prefix sum matrix where each element (i, j) represents the sum of all elements in the submatrix from the top-left corner (0, 0) to (i, j). - For each element (i, j) in the original matrix, calculate the prefix sum as: [ \text{prefixSumMatrix}[i][j] = \text{matrix}[i][j] + \text{left} + \text{above} - \text{aboveLeft} ] where left is the sum to the left, above is the sum above, and aboveLeft is the overlapping area.
2. Sum Region Calculation: - To find the sum of elements in the submatrix defined by (row1, col1) and (row2, col2), use the prefix sum matrix: [ \text{sumRegion} = \text{prefixSumMatrix}[row2][col2] - \text{above} - \text{left} + \text{aboveLeft} ] where above, left, and aboveLeft are the respective sums of the areas outside the submatrix.
3. Edge Cases: - Handle cases where row1 or col1 are zero to avoid accessing out-of-bound indices.

Complexity

Time Complexity:

• The time complexity for constructing the prefix sum matrix is (O(m \times n)), where (m) is the number of rows and (n) is the number of columns.
• Each sumRegion query is answered in (O(1)) time due to the precomputed prefix sum matrix.

Space Complexity:

• The space complexity is (O(m \times n)) for storing the prefix sum matrix, where (m) is the number of rows and (n) is the number of columns.

Code

C++

class NumMatrix {
public:
    NumMatrix(std::vector>& matrix) {
        int rows = matrix.size();
        int cols = matrix[0].size();
        prefixSumMatrix.resize(rows, std::vector(cols, 0));

        for (int i = 0; i < rows; ++i) {
            for (int j = 0; j < cols; ++j) {
                int left = (j > 0) ? prefixSumMatrix[i][j - 1] : 0;
                int above = (i > 0) ? prefixSumMatrix[i - 1][j] : 0;
                int aboveLeft = (i > 0 && j > 0) ? prefixSumMatrix[i - 1][j - 1] : 0;
                prefixSumMatrix[i][j] = matrix[i][j] + left + above - aboveLeft;
            }
        }
    }

    int sumRegion(int row1, int col1, int row2, int col2) {
        int total = prefixSumMatrix[row2][col2];
        int above = (row1 > 0) ? prefixSumMatrix[row1 - 1][col2] : 0;
        int left = (col1 > 0) ? prefixSumMatrix[row2][col1 - 1] : 0;
        int aboveLeft = (row1 > 0 && col1 > 0) ? prefixSumMatrix[row1 - 1][col1 - 1] : 0;

        return total - above - left + aboveLeft;
    }

private:
    std::vector> prefixSumMatrix;
};

Python

class NumMatrix:
    def __init__(self, matrix):
        rows = len(matrix)
        cols = len(matrix[0])
        self.prefixSumMatrix = [[0] * cols for _ in range(rows)]

        for i in range(rows):
            for j in range(cols):
                left = self.prefixSumMatrix[i][j - 1] if j > 0 else 0
                above = self.prefixSumMatrix[i - 1][j] if i > 0 else 0
                aboveLeft = self.prefixSumMatrix[i - 1][j - 1] if i > 0 and j > 0 else 0
                self.prefixSumMatrix[i][j] = matrix[i][j] + left + above - aboveLeft

    def sumRegion(self, row1, col1, row2, col2):
        total = self.prefixSumMatrix[row2][col2]
        above = self.prefixSumMatrix[row1 - 1][col2] if row1 > 0 else 0
        left = self.prefixSumMatrix[row2][col1 - 1] if col1 > 0 else 0
        aboveLeft = self.prefixSumMatrix[row1 - 1][col1 - 1] if row1 > 0 and col1 > 0 else 0

        return total - above - left + aboveLeft

Java

public class NumMatrix {
    private int[][] prefixSumMatrix;

    public NumMatrix(int[][] matrix) {
        int rows = matrix.length;
        int cols = matrix[0].length;
        prefixSumMatrix = new int[rows][cols];

        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                int left = (j > 0) ? prefixSumMatrix[i][j - 1] : 0;
                int above = (i > 0) ? prefixSumMatrix[i - 1][j] : 0;
                int aboveLeft = (i > 0 && j > 0) ? prefixSumMatrix[i - 1][j - 1] : 0;
                prefixSumMatrix[i][j] = matrix[i][j] + left + above - aboveLeft;
            }
        }
    }

    public int sumRegion(int row1, int col1, int row2, int col2) {
        int total = prefixSumMatrix[row2][col2];
        int above = (row1 > 0) ? prefixSumMatrix[row1 - 1][col2] : 0;
        int left = (col1 > 0) ? prefixSumMatrix[row2][col1 - 1] : 0;
        int aboveLeft = (row1 > 0 && col1 > 0) ? prefixSumMatrix[row1 - 1][col1 - 1] : 0;

        return total - above - left + aboveLeft;
    }
}

JavaScript

class NumMatrix {
    constructor(matrix) {
        this.matrix = matrix;
        this.totalSum = [];

        this.prefixSumMatrix(matrix)
    }

    prefixSumMatrix(matrix) {
        for (let i = 0; i < matrix.length; i++) {
            let rowSum = 0;

            for (let j = 0; j < matrix[0].length; j++) {
                const currNum = matrix[i][j];
                matrix[i][j] = currNum + rowSum;
                rowSum += currNum;
            }
            this.totalSum[i] = rowSum;
        }

        this.matrix = matrix;
    }

    // should work in O(1)
    sumRegion(row1, col1, row2, col2) {
        let regionSum = 0;

        for (let row = row1; row <= row2; row++) {
            const currRow = this.matrix[row];
            const rowTotalSum = this.totalSum[row];
            const leftSum = currRow[col1-1] || 0;
            const rightSum =  (rowTotalSum - currRow[col2]) || 0;
            
            regionSum += rowTotalSum - (leftSum + rightSum);
        }

        return regionSum;
    }
}