C# accepted solution


  • 0

    The idea is to store sum value in each cell. Each Update or SumRegion will be O(n) operation.

    /*
    a few ideas I think of,
    1. update becomes O(1) then SumRegion has to scan all of the cells to get the sum. O(m*n).
    2. if each cell value is the sum of rectangle of (0,0) and current cell. 
    	a. Update => O(m*n)
    	b. SumRegion => O(1)
    3. Compromise
    	a. cell value is the sum of first cell to current cell in the same column. 
    	b. it means Update O(m), SumRegion is O(n). 
    	c. because both calls are distributed evenly, it looks good.
    */
    public class NumMatrix {
    	public int[,] sum;
    	public int[,] matrix;
    
        public NumMatrix(int[,] matrix) {
        	this.matrix = matrix;
            sum = new int[matrix.GetLength(0), matrix.GetLength(1)];
            for(int i = 0; i < matrix.GetLength(1); i++) sum[0, i] = matrix[0, i];
    
            for(int i = 1; i < matrix.GetLength(0); i++) {
            	for(int j = 0; j < matrix.GetLength(1); j++) sum[i, j] = sum[i - 1, j] + matrix[i, j];        	
            }
        }
        
        public void Update(int row, int col, int val) {
            var offset = val - matrix[row, col];
            matrix[row, col] = val;
            for(int i = row; i < sum.GetLength(0); i++) sum[i, col] += offset;
        }
        
        public int SumRegion(int row1, int col1, int row2, int col2) {
        	int result = 0;
            for(int col = col1; col <= col2; col++) {
            	result += row1 == 0 ? sum[row2, col] : sum[row2, col] - sum[row1 - 1, col];
            }
            return result;
        }
    }
    
    /**
     * Your NumMatrix object will be instantiated and called as such:
     * NumMatrix obj = new NumMatrix(matrix);
     * obj.Update(row,col,val);
     * int param_2 = obj.SumRegion(row1,col1,row2,col2);
     */
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.