Simple java solution. O(1) time complexity. O(n*n) space complexity.


  • -1

    public class NumMatrix {
    int [][]array;
    public NumMatrix(int[][] matrix) {
    if(matrix==null||matrix.length==0||matrix[0].length==0)
    return;
    int m=matrix.length;
    int n=matrix[0].length;
    array = new int[m][n];
    array[0][0]=matrix[0][0];
    for(int i=1; i<m; i++)
    {
    array[i][0]=array[i-1][0]+matrix[i][0];
    }
    for(int j=1; j<n; j++)
    {
    array[0][j]=array[0][j-1]+matrix[0][j];
    }

        for(int i=1; i<m; i++)
        {
            for(int j=1; j<n; j++)
            {
                array[i][j]=array[i-1][j]+array[i][j-1]-array[i-1][j-1]+matrix[i][j];
            }
        }
        
    }
    
    public int sumRegion(int row1, int col1, int row2, int col2) {
        if(array==null)
            return 0;
        if(row1==0&&col1==0)
            return array[row2][col2];
        if(row1==0)
            return array[row2][col2]-array[row2][col1-1];
        if(col1==0)
            return array[row2][col2]-array[row1-1][col2];
        
        return array[row2][col2]-array[row1-1][col2]-array[row2][col1-1]+array[row1-1][col1-1];
        
    }
    

    }


  • 0
    Y

    Dude...you have two for loops...how can it be O(1) time...


Log in to reply
 

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