JavaScript O(mn) initialize, O(m + n) update, O(min(row2 - row1, col2 - col1)) sum, and O(mn) space using prefix sums


  • 0
    var NumMatrix = function(matrix) {
        if (!matrix.length) return;
        this.matrix = matrix;
        this.rowSums = [];
        this.colSums = [];
        
        for (let r = 0; r < matrix.length; r++) {
            this.rowSums.push([]);
            this.colSums.push([]);
            for (let c = 0; c < matrix[0].length; c++) {
                this.rowSums[r][c] = (r > 0 ? this.rowSums[r - 1][c] : 0) + matrix[r][c];
            }
        }
        
        for (let c = 0; c < matrix[0].length; c++) {
            for (let r = 0; r < matrix.length; r++) {
                this.colSums[r][c] = (c > 0 ? this.colSums[r][c - 1] : 0) + matrix[r][c];
            }
        }
    };
    
    NumMatrix.prototype.update = function(row, col, val) {
        const diff = val - this.matrix[row][col];
        this.matrix[row][col] = val;
        
        for (let r = row; r < this.matrix.length; r++) {
            this.rowSums[r][col] += diff;
        }
        
        for (let c = col; c < this.matrix[0].length; c++) {
            this.colSums[row][c] += diff;
        }
    };
    
    NumMatrix.prototype.sumRegion = function(row1, col1, row2, col2) {
        let sum = 0;
        if (row2 - row1 < col2 - col1) {
            for (let r = row1; r <= row2; r++) {
                sum += this.colSums[r][col2] - (col1 > 0 ? this.colSums[r][col1 - 1] : 0);
            }
        } else {
            for (let c = col1; c <= col2; c++) {
                sum += this.rowSums[row2][c] - (row1 > 0 ? this.rowSums[row1 - 1][c] : 0);
            }
        }
        return sum;
    };
    

    We beat 100% of submissions, but there are few JavaScript submissions at this time. I know the binary indexed tree solution is better, but here is the standard way for anyone who doesn't know about BITs.


Log in to reply
 

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