304. Range Sum Query 2D - Immutable

304. Range Sum Query 2D - Immutable

Given a 2D matrix matrix, handle multiple queries of the following type:

1. Calculate the sum of the elements of matrix inside 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 matrix matrix.

• int sumRegion(int row1, int col1, int row2, int col2) Returns the sum of the elements of matrix inside the rectangle defined by its upper left corner (row1, col1) and lower right corner (row2, col2).

Constraints:

• m == matrix.length

• n == matrix[i].length

• 1 <= m, n <= 200

• -105 <= matrix[i][j] <= 105

• 0 <= row1 <= row2 < m

• 0 <= col1 <= col2 < n

• At most 104 calls will be made to sumRegion.

My Solutions:

Note that the region Sum(OA) is covered twice by both Sum(OB) and Sum(OC).

Sum(ABCD) = Sum(OD) - Sum(OB) - Sum(OC) + Sum(OA)

class NumMatrix {
    
    int[][] sum;

    public NumMatrix(int[][] matrix) {
       if (matrix == null || matrix.length == 0 || matrix[0].length == 0) return;
        
        // make a sum matrix which is one row and one column bigger, for each element, it is the sum of all rectangle starting from (0, 0), ending at the current grid
        sum = new int[matrix.length + 1][matrix[0].length + 1];
        for (int r = 0; r < matrix.length; r++) {
            for (int c = 0; c < matrix[0].length; c++) {
                sum[r + 1][c + 1] = sum[r + 1][c] + sum[r][c + 1] + matrix[r][c] - sum[r][c]; 
            }
        }
    }
    
    // for the requested region, ABCD, sum(ABCD) = sum(OD) - sum(OB) - sum(OC) + sum(OA)
    // point D is at matrix(row2, col2). Because sum is one row and one column bigger, sum(OD) is at sum(row2+1, col2+1)
    // point A is at matrix(row1, col1). Because grid at A should not be included in sum(OA), sum(OA) is at sum(row1, col1)
    // point B is at matrix(row1, col2). sum(OB) should be in the B point above. For example, assume B is at matrix(1, 2), sum(OB) is at sum(1, 3). Therefore, sum(OB) is at sum(row1, col2 + 1)
    // Similar to C
    public int sumRegion(int row1, int col1, int row2, int col2) {
        return sum[row2 + 1][col2 + 1] - sum[row1][col2 + 1] - sum[row2 + 1][col1] + sum[row1][col1];
    }
}

Complexity analysis

• Time complexity : O(1) time per sumRegion query. O(mn) time pre-computation.

• Space complexity: O(mn). The algorithm uses O(mn) space to store the cumulative region sum.