C++ solution space O(mn),

  • 0
    vector<vector<int>> sums;
    int m ;
    int n;
    NumMatrix(vector<vector<int>> &matrix) {
        m = matrix.size();
        if (m==0) return;
        n = matrix[0].size();
        if(n==0) return;
        for(int i =0; i<=m; ++i) sums.emplace_back(vector<int>(n+1, 0));
        for (int i =1; i<=m; ++i)
            for (int j =1; j<=n; ++j)
                sums[i][j] = sums[i-1][j]+sums[i][j-1]-sums[i-1][j-1]+matrix[i-1][j-1];
    int sumRegion(int row1, int col1, int row2, int col2) {
        if (m==0 || n==0) return 0;
        return (sums[row2+1][col2+1]-sums[row2+1][col1]-sums[row1][col2+1]+sums[row1][col1]);

Log in to reply

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