My C++ solution, O(n^2) setup, O(1) sumRegion.


  • 3
    S

    /*
    Conceptually, this code works like this: If we have an initial 'matrix' like the one below

    1 2 1 1

    2 0 1 2

    1 2 1 1

    we calculate the 'presum' matrix below, in which every entry presum(i+1, j+1) is the sum all values in the submatrix matrix(0:i, 0:j)

    0 0 0 0 0

    0 1 3 4 5

    0 3 5 7 10

    0 4 8 11 15

    Then we use sumRegion to add and subtract off blocks until we have the submatrix that we want.
    */

    class NumMatrix {
    private:
       /*************************************************************/
        vector<vector<int> > presum;
    
    public:
        /*************************************************************/
        NumMatrix(vector<vector<int> > &matrix) {
            if (matrix.size() == 0) return;
            
            presum = vector<vector<int> > (matrix.size()+1, vector<int>(matrix[0].size()+1,0));  //initialize as all zeros
            
            //build presum matrix
            for (int i = 1; i < matrix.size()+1; i++){
                for (int j =1; j < matrix[0].size()+1; j++){
                    presum[i][j]=presum[i-1][j]+presum[i][j-1]-presum[i-1][j-1]+matrix[i-1][j-1];
                }
            }
        }
    
        /*************************************************************/
        int sumRegion(int row1, int col1, int row2, int col2) {
           if (presum.size() == 0) return 0;
           int sum=0;
           sum=presum[row2+1][col2+1]-presum[row1][col2+1]-presum[row2+1][col1]+presum[row1][col1];
           return sum;
        }
    };

Log in to reply
 

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