Leetcode 304. Range Sum Query 2D - Immutable (Python)

Related Topic

Dynamic-Programming.

Description

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).

!image

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

Sample I/O

Example 1

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

Note

• You may assume that the matrix does not change.
• There are many calls to sumRegion function.
• You may assume that row1 ≤ row2 and col1 ≤ col2.

Methodology

This question can be sovled as “getting the intersection of set in math”

For example: !image

To get the sum of area D, get the Whole Area sum of area A,B,C,D first. Then Whole Area - B - C + A because area B and area C both include A.

Find the base case:

Create a 2D dp list and init all elements of the first row and first column to 0

Find the pattern:

The area D = Then Whole Area - area B - area C + area A because area B and area C both include A

Answer:

The area D

Code

class NumMatrix:

    def __init__(self, matrix: List[List[int]]):
        if not matrix or not matrix[0]: return None
        row = len(matrix)
        col = len(matrix[0])
        self.dp = [[0]*(col+1) for _ in range(row+1)]
        for i in range(1,row+1):
            for j in range(1,col+1):
                self.dp[i][j]=self.dp[i][j-1]+self.dp[i-1][j]-self.dp[i-1][j-1]+matrix[i-1][j-1]
    def sumRegion(self, row1: int, col1: int, row2: int, col2: int) -> int:
        return self.dp[row2+1][col2+1]-self.dp[row2+1][col1]-self.dp[row1][col2+1]+self.dp[row1][col1]

BigO

Then iterate 2D dp lists, it will cost O(m*n). m is size of row and n is size of column. To get the sum of the region will cost O(1) so total is O(m*n+1)