O(1) Java solution

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

Log in to reply

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