C++ solution, O(MN) space, O(1) time

  • 0

    Using an auxilary array sum to save the sum of the 2-D sub-matrix (i.e. sum[i+1][j+1] is the sum of the sub matrix [0][0] to [i][j]), thus the sum of the submatrix [row1][col1] to [row2][col2] = sum[row2+1][col2+1] - sum[row2+1][col1] - sum[row1][col2+1] + sum[row1][col1]

    class NumMatrix {
        int row=0, col=0;
        vector<vector<int>> sum;
        NumMatrix(vector<vector<int>> &matrix) {
            row = matrix.size();
            col = row==0?0:matrix[0].size();
            sum = vector<vector<int>>(row+1, vector<int>(col+1,0));
            int i,j, rowSum;
            for(i=0; i<row; ++i)
            for(j=0,rowSum=0; j<col; ++j)
                rowSum +=matrix[i][j];
                sum[i+1][j+1] = sum[i][j+1] + rowSum; 
    int sumRegion(int row1, int col1, int row2, int col2) {
        if(!row || !col) return 0;
        return sum[row2+1][col2+1] + sum[row1][col1] - sum[row1][col2+1] - sum[row2+1][col1];


Log in to reply

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