Simple C++ solution


  • 0
    Y

    class NumMatrix {
    public:

    vector<vector<int>> accumulatedMatrix;
    //accumulated matrix stores the accumulated value from each row of matrix
    //ex:
    // matrix: 1 2 3
    //         4 5 6
    //
    // AccumulatedMatrix: 0 1 3 6
    //                    0 4 9 15
    
    
    NumMatrix(vector<vector<int>> &matrix) {
        
        //build the acculatedMatrix
        for(int i=0; i<matrix.size(); ++i)
        {
            vector<int> tmp;
            tmp.push_back(0);
            tmp.push_back(matrix[i][0]);
            for(int j=1; j<matrix[0].size(); ++j)
            {
                tmp.push_back(tmp[j] + matrix[i][j]);
            }
            accumulatedMatrix.push_back(tmp);
        }
    }
    
    int sumRegion(int row1, int col1, int row2, int col2) {
        int sum = 0;
        for(int i=row1; i<=row2; ++i)
        {
            sum += accumulatedMatrix[i][col2+1]-accumulatedMatrix[i][col1];
        }
        return sum;
    }
    

    };

    // Your NumMatrix object will be instantiated and called as such:
    // NumMatrix numMatrix(matrix);
    // numMatrix.sumRegion(0, 1, 2, 3);
    // numMatrix.sumRegion(1, 2, 3, 4);


Log in to reply
 

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