C++ solution beats 100% O(n^2) time and O(1) space


  • 0
    Z
    //Idea: Sum of a column sum[m..n][j] is sum[0...n][j]-matrix[0...m-1][j]
    vector<vector<int>>* matrix_;
    NumMatrix(vector<vector<int>> &matrix) {
        // Each cell stores its vale + elements in the same col above it
        
        // First row is unchanged
        int row = matrix.size();
        for (int i = 1; i < row; ++i) {
            int col = matrix[i].size();
            for (int j = 0; j < col; ++j) {
                matrix[i][j] = matrix[i][j] + matrix[i-1][j];
            }
        }
        matrix_ = &matrix;
    }
    
    // Sum of a column [m..n][j] is matrix[n][j]-matrix[m-1][j]
    int sumRegion(int row1, int col1, int row2, int col2) {
        int row = matrix_->size(), col = 0;
        if (row > 0) {
            col = (*matrix_)[0].size();
        }
        if (row == 0 || col == 0) {
            return 0;
        }
        if (row1 < 0 || row2 >= row || col1 < 0 || col2 >= col) {
            return 0;
        }
        
        int sum = 0;
        for (int j = col1; j <= col2; ++j) {
            int above = 0;
            if (row1 > 0) {
                above = (*matrix_)[row1-1][j];
            }
            sum += (*matrix_)[row2][j] - above;
        }
        return sum;
    }

Log in to reply
 

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