C++ Solution with O(n^2) time complexity for initialization and O(1) time complexity for Query


  • 0
    Y
    class NumMatrix {
    public:
        NumMatrix(vector<vector<int>> &matrix) {
            if(matrix.size() == 0)
                return ;
            sum.resize(matrix.size());
            for(int i = 0; i < matrix.size(); ++ i){
                vector<int> tmpsum(matrix[0].size());
                sum[i] = tmpsum;
                for(int j = 0; j < matrix[0].size(); ++ j){
                    if(!i && !j)
                        sum[i][j] = matrix[0][0];
                    else if(!i)
                        sum[i][j] = sum[i][j - 1] + matrix[i][j];
                    else if(!j)
                        sum[i][j] = sum[i - 1][j] + matrix[i][j];
                    else
                        sum[i][j] = sum[i][j - 1] + sum[i - 1][j] + matrix[i][j] - sum[i - 1][j - 1];
                }
            }
            
        }
    
        int sumRegion(int row1, int col1, int row2, int col2) {
            if(sum.size() == 0)
                return 0;
            if(!row1 && !col1)
                return sum[row2][col2];
            else if(!row1)
                return sum[row2][col2] - sum[row2][col1 - 1];
            else if(!col1)
                return sum[row2][col2] - sum[row1 - 1][col2];
            else
                return sum[row2][col2] - sum[row2][col1 - 1] - sum[row1 - 1][col2] + sum[row1 - 1][col1 - 1];
        }
    private:
    vector<vector<int>> sum;
    };

Log in to reply
 

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