Java solution beats 91.75%


  • 0
    6

    //calcualte sumRegion(0, 0 , i, j) when init the class
    //sumRegion(m, n , i, j) = sumRegion(0, 0 , i, j) - sumRegion(0, 0 , m - 1, j) - sumRegion(0, 0 , i, n - 1) + //sumRegion(0, 0 , m - 1, n - 1)
    //check m - 1 > 0 and n - 1 > 0

    int[][] val;
    
    public NumMatrix(int[][] matrix) {
        if(matrix.length != 0)
        {
            val = new int[matrix.length][matrix[0].length];
            for(int i = 0; i < matrix.length;i++)
            {
                for(int j = 0; j < matrix[0].length; j++)
                {
                    val[i][j] = cal(i,j,matrix);
                }
            }
        }
    }
    
    public int cal(int i, int j, int[][] matrix) {
        if(i == 0 && j == 0) return matrix[0][0];
        if(i == 0) return val[i][j - 1] + matrix[i][j];
        if(j == 0) return val[i - 1][j] + matrix[i][j];
        return val[i-1][j] + val[i][j - 1] - val [i-1][j-1] + matrix[i][j];
    }
    
    public int sumRegion(int row1, int col1, int row2, int col2) {
        int right_top = row1 > 0 ? val[row1-1][col2] : 0;
        int left_bottom = col1 > 0 ? val[row2][col1 - 1]:0;
        int left_top = row1 > 0 && col1 > 0 ? val[row1 - 1][col1 - 1] : 0;
        return val[row2][col2] - right_top - left_bottom + left_top;
    }

Log in to reply
 

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