Massive Algorithms: Matrix Region Sum

Programming Interview Questions 2: Matrix Region Sum | Arden DertatArden Dertat
Given a matrix of integers and coordinates of a rectangular region within the matrix, find the sum of numbers falling inside the rectangle. Our program will be called multiple times with different rectangular regions from the same matrix.
O(1) time, O(MN) space, matrix prefix sum.
http://www.1point3acres.com/bbs/thread-136566-1-1.html
个二维数组，m * n，给一个起点，给一个终点，让把从起点到终点的元素加起来，返回加合（心中窃喜，太简单了）。就说用for循环就行，讲了下最naive的方法，两层循环。写完，问有没有优化，心中有窃喜，把sprial matrix的方法讲了下，以为通过了，谁知面试官说了句：恩，这个不是我想要的，而且感觉复杂度没变。啊啊啊啊啊，难道是我刷题刷错了，这可是我刷得不多的几道题之一啊。这时时间快到了，让我问问题，我就问了优化到底怎么优化，面试官说了什么从四个角那开始，要先pre-process啊，巴拉巴拉，不懂啥意思（还是自己太渣）

$Sum(ABCD) = Sum(OD) - Sum(OB) - Sum(OC) + Sum(OA)$

def precomputeSums(matrix):
    topRow, bottomRow=(0, len(matrix)-1)
    leftCol, rightCol=(0, len(matrix[0])-1)
    sums=[[0]*(rightCol-leftCol+1) for i in range(bottomRow-topRow+1)]
    sums[topRow][leftCol]=matrix[topRow][leftCol]
 
    for col in range(leftCol+1, rightCol+1):
        sums[topRow][col]=sums[topRow][col-1]+matrix[topRow][col]
    for row in range(topRow+1, bottomRow+1):
        sums[row][leftCol]=sums[row-1][leftCol]+matrix[row][leftCol]
 
    for col in range(leftCol+1, rightCol+1):
        columnSum=matrix[topRow][col]
        for row in range(topRow+1, bottomRow+1):
            sums[row][col]=sums[row][col-1]+matrix[row][col]+columnSum
            columnSum+=matrix[row][col]
 
    return sums

Once we have the precomputed sums, we use the above formula to compute the sum of any rectangular region in O(1).

def matrixRegionSum2(matrix, A, D, sums):
    if len(matrix)==0:
        return
 
    if A[0]==0 or A[1]==0:
        OA=0
    else:
        OA=sums[A[0]-1][A[1]-1]
 
    if A[1]==0:
        OC=0
    else:
        OC=sums[D[0]][A[1]-1]
 
    if A[0]==0:
        OB=0
    else:
        OB=sums[A[0]-1][D[1]]
 
    OD=sums[D[0]][D[1]]
 
    return OD-OB-OC+OA

Read full article from Programming Interview Questions 2: Matrix Region Sum | Arden DertatArden Dertat

Matrix Region Sum

Labels

Popular Posts