3 ms Java Solution


  • 4
    W

    standard DP solution. 3 ms, beat 100 %

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

  • 0
    C

    @wangyx05 said in 3 ms Java Solution:

    I have exactly the same idea as yours, however, my implementation is not as optimal as your3, but it will be much easier for everyone to understand. I will also explain the idea below with an example:
    A 3*3 grids, we try to get a dp array as left

    1 2 3      1  3  6
    4 5 6  ->  5 12 21
    7 8 9      12 27 45
    

    The transform formula is: dp[i][j] = dp[i-1][j] + dp[j-1][i] - dp[i-1][j-1]

    Then how can we use this dp array to calculate a 2D range? The formula is (I draw a few grids to get the following formula):
    res = dp[row2][col2] - dp[row1-1][col2] - dp[row2,col1-1] + dp[row1-1][col1-1]

    So the implementation is as following:

    class NumMatrix {
    
        private int[][] dp;
        
        public NumMatrix(int[][] matrix) {
            
            if (null == matrix || 0 == matrix.length)
                dp = new int[0][0];
            else 
                dp = new int[matrix.length][matrix[0].length];
            
            // build the dp array dp[i][j] = dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1](all in range)
            for (int i = 0; i < dp.length; i ++)
                for (int j = 0; j < dp[0].length ; j ++) {
       
                    dp[i][j] = matrix[i][j];
                    if (i - 1 >= 0) 
                        dp[i][j] += dp[i - 1][j];
                    if (j - 1 >= 0)
                        dp[i][j] += dp[i][j - 1];
                    if (i - 1 >= 0 && j - 1 >= 0)
                        dp[i][j] -= dp[i - 1][j - 1];
                }
        }
        
        public int sumRegion(int row1, int col1, int row2, int col2) {
            
            int sum = dp[row2][col2];
            if (row1 - 1 >= 0)
                sum -= dp[row1 - 1][col2];
            if (col1 - 1 >= 0)
                sum -= dp[row2][col1 - 1];
                
            return sum += (row1 - 1 >= 0 && col1 - 1 >= 0) ? dp[row1 - 1][col1 - 1] : 0;
        }
    }
    

Log in to reply
 

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