LeetCode 304. Range Sum Query 2D – Immutable

Problem

To extend the 1D range query problem to 2D, we can still use the same cache approach but with a new “2D” formula.

The new formula for calculating area E will become

E = A – B – C + D

Being translated to the matrix language, it will be:

sum[ (row2,col2) – (row1,col1)] = sum[row2, col2] – sum[row2, col1-1] – sum[row1-1, col2] + sum[row1-1, col1-1]

Where sum[i,j] is the summation of numbers in the rectangle between (0, 0) and (i, j).

My code:

public class NumMatrix {
    int[,] sums;
    
    public NumMatrix(int[,] matrix) {
        int height = matrix.GetLength(0);
        int width = matrix.GetLength(1);
        sums = new int[height, width];
        for(int i = 0; i < height; i++){
            for(int j = 0; j < width; j++){ 
                if(i == 0 && j == 0) { sums[i,j] = matrix[i,j]; } 
                else if (i == 0 && j > 0) { sums[i,j] = matrix[i,j] + sums[i,j-1]; }
                else if (i > 0 && j == 0) { sums[i,j] = matrix[i,j] + sums[i-1,j]; }
                else { sums[i,j] = matrix[i,j] + sums[i-1,j] + sums[i,j-1] - sums[i-1,j-1]; }
            }
        }    
    }
    
    public int SumRegion(int row1, int col1, int row2, int col2) {
        if(row1 == 0 && col1 == 0) { return sums[row2, col2]; }
        else if (row1 == 0 && col1 > 0) { return sums[row2,col2] - sums[row2, col1-1]; }
        else if (row1 > 0 && col1 == 0) { return sums[row2,col2] - sums[row1-1, col2]; }
        else { return sums[row2, col2] - sums[row2, col1-1] - sums[row1-1, col2] + sums[row1-1, col1-1]; }
    }
}

/**
 * Your NumMatrix object will be instantiated and called as such:
 * NumMatrix obj = new NumMatrix(matrix);
 * int param_1 = obj.SumRegion(row1,col1,row2,col2);
 */

Note that I need to specially handle the edge case (row or column equal to zero) in my code.

Leave a Reply

Your email address will not be published. Required fields are marked *