Sharing My Python solution


  • 9
    F

    The idea is simple, just precompute sums for all matrices with (0, 0) as top left corner and (i, j) as bottom right corner. There are O(n^2) of these matrices, so we store them in a 2D table. In order to make code simpler, I add an extra column and row, filled with 0.

    class NumMatrix(object):
          def __init__(self, matrix):
              if matrix is None or not matrix:
                  return
              n, m = len(matrix), len(matrix[0])
              self.sums = [ [0 for j in xrange(m+1)] for i in xrange(n+1) ]
              for i in xrange(1, n+1):
                  for j in xrange(1, m+1):
                      self.sums[i][j] = matrix[i-1][j-1] + self.sums[i][j-1] + self.sums[i-1][j] - self.sums[i-1][j-1]
        
    
          def sumRegion(self, row1, col1, row2, col2):
              row1, col1, row2, col2 = row1+1, col1+1, row2+1, col2+1
              return self.sums[row2][col2] - self.sums[row2][col1-1] - self.sums[row1-1][col2] + self.sums[row1-1][col1-1]

  • 0
    P

    +1. However, a tiny issue is the NumMatrix object is initialized with empty matrix, then the self.sums would be undefined and the method sumRegion would raise error.


  • 0
    F

    Yeah, I am aware of that. But since those are just trivial codes and it seems that there are no test case to cover this situation, I just ignore them here:-)


Log in to reply
 

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