c++ slow (570ms) summed area tables


  • 0
    G
    class NumMatrix 
    {
    public:
        vector<vector<int>> mat;
        vector<vector<int>> table;
        int numRows;
        int numCols;
    
        NumMatrix(vector<vector<int>> &matrix)
        : mat(matrix)
        , numRows(matrix.size())
        , numCols(numRows > 0 ? matrix[0].size() : 0)
        {
            table.resize(numRows);
            for(r : table)
            {
                r.resize(numCols);
            }
            
            for(int i = 0; i < numRows; ++i)
            {
                for(int j = 0; j < numCols; ++j)
                {
                    int sum = matrix[i][j];
                    if(i > 0)
                    {
                        sum += table[i-1][j];
                    }
                    if(j > 0)
                    {
                        sum += table[i][j-1];
                    }
                    if((i > 0) && (j > 0))
                    {
                        sum -= table[i-1][j-1];
                    }
                    table[i][j] = sum;
                }
            }
        }
    
        void update(int row, int col, int val) 
        {
            int difference = val - mat[row][col];
            mat[row][col] = val;
            
            for(int i = row; i < numRows; ++i)
            {
                for(int j = col; j < numCols; ++j)
                {
                    table[i][j] += difference;
                }
            }
        }
    
        int sumRegion(int row1, int col1, int row2, int col2) 
        {
            if(numRows == 0 || numCols == 0)
            {
                return 0;
            }
            
            int sum = table[row2][col2];
            if(row1 > 0)
            {
                sum -= table[row1-1][col2];
            }
            if(col1 > 0)
            {
                sum -= table[row2][col1-1];
            }
            if((row1 > 0) && (col1 > 0))
            {
                sum += table[row1-1][col1-1];
            }
            
            return sum;
        }
    };
    

Log in to reply
 

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