Sharing of my c++ solution with O(2*m*n) of time for init and O(1) of time for query.


  • 0
    R
    class NumMatrix {
    public:
        NumMatrix(vector<vector<int>> &matrix) {
            int m=matrix.size();
            int n=m>0?matrix[0].size():0;
            for(int i=0;i<m;i++) {
                vector<int> row;
                for(int j=0;j<n;j++) {
                    if(j==0)
                        row.push_back(matrix[i][j]);
                    else
                        row.push_back(matrix[i][j]+row[j-1]);
                }
                rowSum.push_back(row);
            }
            for(int j=0;j<n;j++) {
                vector<int> col;
                for(int i=0;i<m;i++) {
                    if(i==0)
                        col.push_back(rowSum[i][j]);
                    else
                        col.push_back(rowSum[i][j]+col[i-1]);
                }
                regionSum.push_back(col);
            }
        }
        int sumRegion(int row1, int col1, int row2, int col2) {
            int tl,left,up;
            tl= row1-1>=0&&col1-1>=0 ? regionSum[col1-1][row1-1]:0;
            left=col1-1>=0 ? regionSum[col1-1][row2]:0;
            up=row1-1>=0 ? regionSum[col2][row1-1]:0;
            return regionSum[col2][row2]-left-up+tl;
        }
    private:
        vector<vector<int>> rowSum;
        vector<vector<int>> regionSum;
    };

Log in to reply
 

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