Java Solution using cumulative sum


  • 0
    R

    I'm storing the cumulative sum for each row in a separate matrix i.e dp.
    Since I'm supposed to find the sum in between two rows,
    I can do that using "sum =sum + (dp[row2][i] - dp[rowPrev][i])"
    where rowPrev is the row before row1, thus containing cumulative sum until the row before row1
    and i is the range between col1 and col2.

     public class NumMatrix {
                
                int[][] dp;
                
                public NumMatrix(int[][] matrix) {
                   if(matrix.length == 0 || matrix[0].length ==0 ){
                    return; 
                   }
                   dp = new int[matrix.length][matrix[0].length];
                   for(int j=0;j<matrix[0].length;j++){
                       dp[0][j] = matrix[0][j];
                   }
                   for(int i=1;i<dp.length;i++){
                       for(int j=0;j<dp[0].length;j++){
                           dp[i][j] = dp[i-1][j] + matrix[i][j];
                       }
                   }
                }
        
        
        
        public int sumRegion(int row1, int col1, int row2, int col2) {
                    
                    if(row1<0 || row2<0 || col1<0 || col2<0)
                    return -1;
                    int sum = 0;
                    int rowPrev = row1-1;
                    if(rowPrev < 0){
                        for(int i=col1;i<=col2;i++){
                            sum  = sum + dp[row2][i];
                        }
                    }
                    
                    else{
                        for(int i=col1;i<=col2;i++){
                            sum =sum + (dp[row2][i] - dp[rowPrev][i]);
                        }
                    }
                    return sum;
                }
            }

Log in to reply
 

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