Leetcode: Range Sum Query 2D – Immutable

Range Sum Query 2D – Immutable



Similar Problems:


Given a 2D matrix matrix, find the sum of the elements inside the rectangle defined by its upper left corner (row1, col1) and lower right corner (row2, col2).

Range Sum Query 2D
The above rectangle (with the red border) is defined by (row1, col1) = (2, 1) and (row2, col2) = (4, 3), which contains sum = 8.

Example:

Given matrix = [
  [3, 0, 1, 4, 2],
  [5, 6, 3, 2, 1],
  [1, 2, 0, 1, 5],
  [4, 1, 0, 1, 7],
  [1, 0, 3, 0, 5]
]

sumRegion(2, 1, 4, 3) -> 8
sumRegion(1, 1, 2, 2) -> 11
sumRegion(1, 2, 2, 4) -> 12

Note:

  1. You may assume that the matrix does not change.
  2. There are many calls to sumRegion function.
  3. You may assume that row1 <= row2 and col1 <= col2.

Github: code.dennyzhang.com

Credits To: leetcode.com

Leave me comments, if you have better ways to solve.


## Blog link: https://code.dennyzhang.com/range-sum-query-2d-immutable
class NumMatrix(object):
    ## Idea: Maintain a matrix: value[i][j] = sum(matrix[0][0] to matrix[i][j]). 
    ##       Thus we can get the sum in Time O(1)
    ## Complexity:
    def __init__(self, matrix):
        """
        :type matrix: List[List[int]]
        """
        self.is_empty = False
        if matrix is None:
            self.is_empty = True
            return
        height = len(matrix)
        if height == 0:
            self.is_empty = True
            return

        width = len(matrix[0])
        self.sum_matrix = []*height
        for i in range(0, height):
            self.sum_matrix.append([0]*width)
        # calculate the sum
        for i in range(0, height):
            for j in range(0, width):
                if i == 0:
                    self.sum_matrix[i][j] = 0
                    for k in range(0, j+1):
                        self.sum_matrix[i][j] += matrix[i][k]
                elif j == 0:
                    self.sum_matrix[i][j] = 0
                    for k in range(0, i+1):
                        self.sum_matrix[i][j] += matrix[k][j]
                else:
                    self.sum_matrix[i][j] = matrix[i][j] \
                                + self.sum_matrix[i-1][j] \
                                + self.sum_matrix[i][j-1] \
                                - self.sum_matrix[i-1][j-1]

    def sumRegion(self, row1, col1, row2, col2):
        """
        :type row1: int
        :type col1: int
        :type row2: int
        :type col2: int
        :rtype: int
        """
        if self.is_empty:
            return None
        else:
            return self.sum_matrix[row2][col2] \
                    - (self.sum_matrix[row1-1][col2] if row1>0 else 0) \
                    - (self.sum_matrix[row2][col1-1] if col1>0 else 0) \
                    + (self.sum_matrix[row1-1][col1-1] if row1>0 and col1>0 else 0)

# Your NumMatrix object will be instantiated and called as such:
# obj = NumMatrix(matrix)
# param_1 = obj.sumRegion(row1,col1,row2,col2)
linkedin
github
slack

Share It, If You Like It.

Leave a Reply

Your email address will not be published.