15ms easy to understand java solution


  • 58
    L

    We use colSums[i][j] = the sum of ( matrix[0][j], matrix[1][j], matrix[2][j],......,matrix[i - 1][j] ).

    private int[][] colSums;
    private int[][] matrix;
    
    public NumMatrix(int[][] matrix) {
        if(   matrix           == null
           || matrix.length    == 0
           || matrix[0].length == 0   ){
            return;   
         }
         
         this.matrix = matrix;
         
         int m   = matrix.length;
         int n   = matrix[0].length;
         colSums = new int[m + 1][n];
         for(int i = 1; i <= m; i++){
             for(int j = 0; j < n; j++){
                 colSums[i][j] = colSums[i - 1][j] + matrix[i - 1][j];
             }
         }
    }
    //time complexity for the worst case scenario: O(m)
    public void update(int row, int col, int val) {
        for(int i = row + 1; i < colSums.length; i++){
            colSums[i][col] = colSums[i][col] - matrix[row][col] + val;
        }
        
        matrix[row][col] = val;
    }
    //time complexity for the worst case scenario: O(n)
    public int sumRegion(int row1, int col1, int row2, int col2) {
        int ret = 0;
        
        for(int j = col1; j <= col2; j++){
            ret += colSums[row2 + 1][j] - colSums[row1][j];
        }
        
        return ret;
    }

  • 0
    A
    This post is deleted!

  • 0
    L

    I did not say this is the optimal solution, moreover I did not see my solution was as good as you said, O(n ^1/2). I have mentioned the time complexity of the worst case scenario for Update Sumregion in my code.

    Anyways it would be great if you could offer O(logn) solution. Please take into account that "the number of calls to update and sumRegion function is distributed evenly". Hopefully your solution would be able to take care of the performance of both Update and Sumregion. Actually that was where I got stuck.


  • 0
    Y

    The code is really easy to understand. But i am not sure why you transfer sum of cols to a row based matrix, which makes me really confused in the beginning.


  • 0
    L

    that is really a good point. It is just my bad. I should have been consistent. Thank you for pointing that out. I will update the code accordingly.


  • 2
    A

    wow, this is just brilliant! Perfectly splits operations complexity between update and request operations, and so easy :)


  • -3

    @larrywang2014 The most concise and easy to understand BIT implementation.


  • -1
    L

    @CodingSlug I don't think there is any BIT operations here. But this is a nice solution. I see that this runs faster (15ms) than someone else's 2D BIT implementation (17ms).


  • 0
    S

    @CodingSlug This is not BIT at all.


  • 0
    B

    Awesome solution!


  • 2
    A

    Isn't it unrealistic to expect people to write BIT during an interview?


  • 5
    S

    This can be improved to O(1) space. I changed it to row sum version. BTW I think this solution is better than the BIT version since it's quite hard to give a BIT solution during an interview (unless you have seen BIT before).

    public class NumMatrix {
        // O(1) space
        int[][] mMatrix = null;
        int m = 0;
        int n = 0;
        
        public NumMatrix(int[][] matrix) {
            if (matrix == null || matrix.length == 0 || matrix[0].length == 0) return;
            mMatrix = matrix;
            m = matrix.length;
            n = matrix[0].length;
            // rowSums[i][j] = rowSums[i][0] + rowSums[i][1] + ... + rowSums[i][j]
            for (int i = 0; i < m; i++) {
                for (int j = 1; j < n; j++) {
                    matrix[i][j] = matrix[i][j] + matrix[i][j - 1];
                }
            }
        }
        // O(n)
        public void update(int row, int col, int val) {
            // handle col = 0 differently
            int originalValue = col == 0 ? mMatrix[row][0] : mMatrix[row][col] - mMatrix[row][col - 1];
            int diff = val - originalValue;
            for (int j = col; j < n; j++) {
                mMatrix[row][j] += diff;
            }
        }
        // O(m)
        public int sumRegion(int row1, int col1, int row2, int col2) {
            int result = 0;
            for (int i = row1; i <= row2; i++) {
                // handle col = 0 differently
                result += col1 == 0 ? mMatrix[i][col2] : mMatrix[i][col2] - mMatrix[i][col1 - 1];
            }
            return result;
        }
    }
    

  • 0
    R

Log in to reply
 

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