My O(1) solution in C++, 268 ms


  • 0
    P
    class NumMatrix {
    public:
        NumMatrix(vector<vector<int>> &matrix) 
        {
            for(int i=0; i<matrix.size(); i++)
            {
                tmp.push_back(vector<int>(matrix[0].size(), 0));
                for(int j=0; j<matrix[0].size(); j++)
                {
                    if(i==0 && j==0)
                        tmp[i][j] = matrix[i][j];
                    else if(i==0)
                        tmp[i][j] = tmp[i][j-1] + matrix[i][j];
                    else if(j==0)
                        tmp[i][j] = tmp[i-1][j] + matrix[i][j];
                    else
                        tmp[i][j] = tmp[i-1][j] + tmp[i][j-1] - tmp[i-1][j-1] + matrix[i][j];
                }
            }
        }
    
        int sumRegion(int row1, int col1, int row2, int col2) 
        {
            int res;
            if(row1==0 && col1==0)
                res = tmp[row2][col2];
            else if(row1 == 0)
                res = tmp[row2][col2] - tmp[row2][col1-1];
            else if(col1 == 0)
                res = tmp[row2][col2] - tmp[row1-1][col2];
            else
                res = tmp[row2][col2] + tmp[row1-1][col1-1] - (tmp[row1-1][col2] + tmp[row2][col1-1]);
            return res;
        }
        
        vector<vector<int>> tmp;
    };
    

    Is there any other quicker solution?


Log in to reply
 

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