Python solution with detailed explanation


  • 0
    G

    Solution

    Range Sum Query 2D - Immutable https://leetcode.com/problems/range-sum-query-2d-immutable/

    Refer Editorial to for solutions: All worth it

    • Naive - compute at run time
    • Pre-compute every possibility = m^2 * n^2
    • Build a cdf array row or column wise. Depending on this choice, the run time complexity will matter - will be either O(m) or O(n). If rows are more, choose caching row wise so that query complexity is column wise.
    • Optimized caching - caching with respect to index 0,0.
      Notice the DP equation to compute: Sum(ABCD)=Sum(OD)−Sum(OB)−Sum(OC)+Sum(OA)
      Notice also the code to build the matrix uses DP
    • dp[r + 1,c + 1] = dp[r + 1,c] + dp[r,c + 1] + matrix[r,c] - dp[r,c];
    class NumMatrix(object):
        def __init__(self, matrix):
            """
            initialize your data structure here.
            :type matrix: List[List[int]]
            """
            M = len(matrix)
            if M == 0:
                return
            N = len(matrix[0])
            self.cdf = [[0]*N for _ in range(M)]
            self.matrix = matrix
            # Column wise cache
            for j in range(N):
                for i in range(M):
                    if i == 0:
                        self.cdf[i][j] = matrix[i][j]
                    else:
                        self.cdf[i][j] = self.cdf[i-1][j] + matrix[i][j]
            return
            
    
        def sumRegion(self, row1, col1, row2, col2):
            """
            sum of elements matrix[(row1,col1)..(row2,col2)], inclusive.
            :type row1: int
            :type col1: int
            :type row2: int
            :type col2: int
            :rtype: int
            """
            result = 0
            for col in range(col1, col2+1):
                result = result + self.cdf[row2][col]-self.cdf[row1][col]+self.matrix[row1][col]
            return result
    

Log in to reply
 

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