Sharing my 504ms C++ solution


  • 0
    T
    class NumMatrix {
    private:
        vector<vector<int>> myMatrix; 
        vector<vector<int>> myColSum;
        // mycolSum[i+1][j] = matrix[0][j]+matrix[1][j]+...+matrix[i][j]
        int m;
        int n;
        
    public:
        NumMatrix(vector<vector<int>> &matrix) {
            myMatrix = matrix;
            
            m = myMatrix.size();
            if(m==0)
                return;
            n = myMatrix[0].size();
            if(n==0)
                return;
                
            myColSum.resize(m+1, vector<int>(n, 0));
            int i, j;
            for(i=0; i<m; i++)
                for(j=0; j<n; j++)
                    myColSum[i+1][j] = myColSum[i][j] + matrix[i][j];
        }
    
        void update(int row, int col, int val) {
            int tmp = myMatrix[row][col];
            myMatrix[row][col] = val;
            for(int i=row+1; i<=m; i++)
                myColSum[i][col] = myColSum[i][col] + val - tmp;
        }
    
        int sumRegion(int row1, int col1, int row2, int col2) {
            int result=0;
            int j;
            for(j=col1; j<=col2; j++)
                result += (myColSum[row2+1][j] - myColSum[row1][j]);
                
            return result;
        }
    };
    
    
    // Your NumMatrix object will be instantiated and called as such:
    // NumMatrix numMatrix(matrix);
    // numMatrix.sumRegion(0, 1, 2, 3);
    // numMatrix.update(1, 1, 10);
    // 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.