Python straightforward DP solution


  • -1
    F

    No need to add additional columns or rows for edge cases. First, calculate the sum of the first row(matrix[0][0-n]) and the first column matrix[0-n][0], then start from matrix[1][1] to get all sums each from [0][0] to [i][j], then do some simple geometry calculation: s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+matrix[i][j], finally, we just need to get rid of the edge cases by simply check if i or j is less than zero.

    class NumMatrix(object):
    def __init__(self, matrix):
        if not matrix: return
        s=[[None for i in xrange(len(matrix[0]))] for j in xrange(len(matrix))]
        s[0][0]=matrix[0][0]
        for i in xrange(1,len(matrix[0])):
            s[0][i]=matrix[0][i]+s[0][i-1]
        for i in xrange(1,len(matrix)):
            s[i][0]=matrix[i][0]+s[i-1][0]
        for i in xrange(1,len(matrix)):
            for j in xrange(1,len(matrix[0])):
                s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+matrix[i][j]
        self.s=s
    
    def sumRegion(self, row1, col1, row2, col2):
        s=self.s
        #edge cases checking
        if row1-1<0:
            s1=0
        else:
            s1=s[row1-1][col2]
        if col1-1<0:
            s2=0
        else:
            s2=s[row2][col1-1]
        if row1-1<0 or col1-1<0:
            s3=0
        else:
            s3=s[row1-1][col1-1]
        
        return s[row2][col2]-s1-s2+s3

Log in to reply
 

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