C++ easy to understand implementation - beat 88%


  • 1

    My solution simply caches the cumulative sum of each row. Whenever there is an update at (i,j), just update ith row's cumulative sum from position j. i.e ( j - col ) computations every update.

    Time complexity of getting sum of a region: O(N), N = # of rows
    Time complexity of updating an value: O(M), M = # of cols

    class NumMatrix {
    public:
        NumMatrix(vector<vector<int>> matrix) {
            int width = matrix.size();
            if( width == 0 ) return;
            int height = matrix[0].size();
            mData = matrix;
            mRowCumulative = vector<vector<int>>( width, vector<int>(height, 0) );
            for( int i = 0; i < width; i++)
            {
                int sum = mData[i][0];
                mRowCumulative[i][0] = sum;
                for( int j = 1; j < height; j++)
                {
                    sum += mData[i][j];
                    mRowCumulative[i][j] = sum;
                }
            }
        }
        
        void update(int row, int col, int val) {
            mData[row][col] = val;
            for( int j = col; j < mData[row].size(); j++)
            {
                int prev_sum = j == 0 ? 0 : mRowCumulative[row][j-1];
                mRowCumulative[row][j] = prev_sum + mData[row][j];
            }
        }
        
        int sumRegion(int row1, int col1, int row2, int col2) {
            int sum = 0;
            for( int i = row1; i <= row2; i++)
            {
                int prev_sum = col1 == 0 ? 0 : mRowCumulative[i][col1-1];
                sum += mRowCumulative[i][col2] - prev_sum;
            }
            return sum;
        }
    private:
        vector<vector<int>> mData;
        vector<vector<int>> mRowCumulative;
    };
    
    /**
     * Your NumMatrix object will be instantiated and called as such:
     * NumMatrix obj = new NumMatrix(matrix);
     * obj.update(row,col,val);
     * int param_2 = obj.sumRegion(row1,col1,row2,col2);
     */
    

  • 0

    Nice Solution. Not sure why this solution can be so quick.


Log in to reply
 

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