Java 14ms O(1) space row sum solution without BIT


  • 3
    S

    This solution is inspired by https://discuss.leetcode.com/topic/30250/15ms-easy-to-understand-java-solution. I added some improvements. BTW 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;
        }
    }
    

Log in to reply
 

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