Clean and easy to understand java solution


  • 62
    L
    private int[][] dp;
    
    public NumMatrix(int[][] matrix) {
        if(   matrix           == null
           || matrix.length    == 0
           || matrix[0].length == 0   ){
            return;   
        }
        
        int m = matrix.length;
        int n = matrix[0].length;
        
        dp = new int[m + 1][n + 1];
        for(int i = 1; i <= m; i++){
            for(int j = 1; j <= n; j++){
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1] -dp[i - 1][j - 1] + matrix[i - 1][j - 1] ;
            }
        }
    }
    
    public int sumRegion(int row1, int col1, int row2, int col2) {
        int iMin = Math.min(row1, row2);
        int iMax = Math.max(row1, row2);
        
        int jMin = Math.min(col1, col2);
        int jMax = Math.max(col1, col2);
        
        return dp[iMax + 1][jMax + 1] - dp[iMax + 1][jMin] - dp[iMin][jMax + 1] + dp[iMin][jMin];    
    }

  • 2

    Thanks for sharing this solution! :)


  • 4
    L

    dp = new int[m+1][n+1]; is awesome! I wrote a lot of if functions = =|||


  • 18

    Nice solution! One minor thing. Notice assumption 3: You may assume that row1 ≤ row2 and col1 ≤ col2.
    Anyway it's always nice to have the Math.min step.

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

  • 3
    L

    That assumption was not there before I came up with my solution. It was added later. However I did think about whether or not I wanted to remove those Math.min statements after that assumption was added.

    Considering the fact that these Math.min statements would not cause dramatic performance penalty and the principle that never trust user inputs, I decided to leave them there as some very basic precaution measure.


  • 3
    E

    improve the space from O(mn) to O(1) by using the matrix to store DP since:

    Note 1. "You may assume that the matrix does not change."

    public class NumMatrix {
    private int[][] dp;
        public NumMatrix(int[][] matrix) {
            for (int i = 0; i < matrix.length; i++) {
                for (int j = 0; j < matrix[0].length; j++) {
                    int left = (j == 0) ? 0 : matrix[i][j - 1];
                    int up = (i == 0) ? 0 : matrix[i - 1][j];
                    int corner = (i == 0 || j == 0) ? 0 : matrix[i - 1][j - 1];
                    matrix[i][j] += (left + up - corner);
                }
            }
            dp = matrix;
        }
    
        public int sumRegion(int row1, int col1, int row2, int col2) {
            int left = (row1 > 0) ? dp[row1 - 1][col2] : 0;
            int up = (col1 > 0) ? dp[row2][col1 - 1] : 0;
            int corner = (row1 > 0 && col1 > 0) ? dp[row1 - 1][col1 - 1] : 0;
            return dp[row2][col2] - left - up + corner;
        }
    }

  • 0
    V

    No need to create a larger matrix.

    public class NumMatrix {
        int[][] mat;
    
        public NumMatrix(int[][] matrix) {
            mat = matrix;
            for(int i = 0; i < matrix.length; i++){
                for(int j = 0; j < matrix[0].length; j++){
                    mat[i][j] += (j>0 ? mat[i][j-1] : 0) + (i>0 ? mat[i-1][j] : 0) - (i>0&&j>0?mat[i-1][j-1]:0);
                }
            }
        }
    
        public int sumRegion(int row1, int col1, int row2, int col2) {
            return mat[row2][col2] - (col1>0 ? mat[row2][col1-1]:0) - (row1>0?mat[row1-1][col2]:0) + (col1>0 && row1>0 ? mat[row1-1][col1-1]:0);
        }
    }

  • 0
    A
    This post is deleted!

  • 0
    U

    Maybe shouldnt check both
    matrix.length == 0
    || matrix[0].length == 0


  • 2
    R

    I can't understand this question. What does it want me to do ?
    why not for traverse from (row1,co1) to (row2,col2)?
    somebody help me out.


  • 2
    A

    @ricace the idea is that for one given matrix, the user is going to perform a lot of sum calculations, so instead of retraversing the matrix everytime he asks for a sum, we calculate once and for all the sum from the origin to each cell and store them in a matrix then the sum from any point to another can be easily calculated fast from this matrix. So the sum method works in O(1), just the construction is O(n*m)


  • 0

    @lingjiadeng Me too.

        public int sumRegion(int row1, int col1, int row2, int col2) {
            if(col1>0&&row1>0) return sum[row2][col2]-sum[row2][col1-1]-sum[row1-1][col2]+sum[row1-1][col1-1];
            if(col1==0&&row1==0) return sum[row2][col2];
            if(col1==0) return sum[row2][col2]-sum[row1-1][col2];
            if(row1==0) return sum[row2][col2]-sum[row2][col1-1];
            return 0;
        }
    

Log in to reply
 

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