C++ In-place solution


  • 0
    W
    class NumMatrix {
    public:
        NumMatrix(vector<vector<int>> &matrix) : A(matrix) {
            if (A.empty()) return;
            auto m = A.size(), n = A[0].size();
            for (int i = 1; i < m; ++i) A[i][0] += A[i - 1][0];
            for (int j = 1; j < n; ++j) A[0][j] += A[0][j - 1];
            for (int i = 1; i < m; ++i) for (int j = 1; j < n; ++j)
                A[i][j] += A[i - 1][j] + A[i][j - 1] - A[i - 1][j - 1];
        }
    
        int sumRegion(int r1, int c1, int r2, int c2) {
            return sum(r2, c2) - sum(r1 - 1, c2) - sum(r2, c1 - 1) + sum(r1 - 1, c1 - 1);
        }
    private:
        int sum(int r, int c) {
            return r < 0 || c < 0 ? 0 : A[r][c];
        }
        vector<vector<int>> &A;
    };
    

Log in to reply
 

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