13ms update() O(n), sumRegion() O(m) time row sum JAVA solution


  • 4
    Q

    If we are going to calculate the whole sum every time the sumRegion function get called, it will introduce a lot of redundant calculation. Think of 3 situations:

    1. There are a lot of sumRegion function call but very little update function call.
      So you want to move all the heavy calculations into update function call. To do this, you have to maintain a diagnose sum matrix and the sumRegion will take O(1) time because you just need to return the value in your buffer which you calculated in update function

    2. There are a lot of update but only a few sumRegion function call.
      Just update the original matrix and calculate everytime, update function take O(1) time

    3. As this problem indicates, the update and sumRegion function calls are distributed evenly.
      What you want to do is to distribute some of the work to update function and some of other work to sumRegion function so that both of the function will take less than O(mn) time
      You can do this by maintaining a row sum matrix. When a cell gets updated, only update the row sum in the same row which takes O(n) time where n is the length of the matrix
      When sumRegion function gets called just add all the row sum with a small trick and it takes O(m) time where m is the height of the matrix

    public class NumMatrix {
        int[][] matrix;
        int[][] lSumMatrix;
        public NumMatrix(int[][] matrix) {
            this.matrix = matrix;
            int h = matrix.length;
            if (h > 0) {
                lSumMatrix = new int[h][matrix[0].length]; 
                for (int i = 0; i < lSumMatrix.length; ++i) {
                    lSumMatrix[i][0] = matrix[i][0];
                    for (int j = 1; j < lSumMatrix[i].length; ++j) {
                        lSumMatrix[i][j] = lSumMatrix[i][j-1]+matrix[i][j];
                    }
                }
            }
        }
        public void update(int row, int col, int val) {
            int tv = val-matrix[row][col];
            matrix[row][col] = val;
            for (int j = col; j < lSumMatrix[row].length; ++j) {
                lSumMatrix[row][j] += tv;
            }
        }
        public int sumRegion(int row1, int col1, int row2, int col2) {
            int sum = 0;
            for (int i = row1; i <= row2; ++i) {
                sum += (lSumMatrix[i][col2]-(col1>0?lSumMatrix[i][col1-1]:0));
            }
            return sum;
        }
    }

Log in to reply
 

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