Submatrix Sum

LintCode 405

Given an integer matrix, find a submatrix where the sum of numbers is zero. Your code should return the coordinate of the left-up and right-down number.

Example

Given matrix

[
  [1 ,5 ,7],
  [3 ,7 ,-8],
  [4 ,-8 ,9],
]

return[(1,1), (2,2)]

Challenge

O(n^3) time.

求 submatrix sum，可以用 Range Sum Query 2D - Immutable 的方法，就是先求个类似prefixsum[i][j]数组。

然后对 row1, col2, row2, col2 来做4重循环，求 sum 为0的 submatrix。这样的话时间复杂度是 O(N^4)，而题目要求O(N^3)。看了下九章的答案，做的比较巧妙，对 row1, row2 循环，然后对 col 循环，一边循环一边把 sum 放在 hash map 的。然后对照。具体需要看code

    def submatrixSum(self, matrix):
        # 没做做数组为空的检查，认为test case 给有效的matrix
        m, n = len(matrix), len(matrix[0])
        accu = [ [0] * (n + 1) for _ in xrange(m + 1)]
        for i in xrange(1, m + 1):
            for j in xrange(1, n + 1):
                accu[i][j] = accu[i - 1][j] + accu[i][j - 1] \
                             + matrix[i - 1][j - 1] - accu[i - 1][j - 1]

        for lo in xrange(m + 1):
            for hi in xrange(lo + 1, m + 1):
                hashmap = dict()
                for j in xrange(n + 1):
                    target = accu[hi][j] - accu[lo][j]    # 就如一维数组的情况下，希望找到前面有相同的 prefix sum
                    if target in hashmap:                 # 那么两个坐标之间的 sub array sum = 0
                        k = hashmap[target]               # 这里是类似的思想，在lo和hi确定的情况下，把lo和hi夹着的长条
                        return [(lo, k), (hi - 1, j - 1)] # 当作1维来处理
                    else:
                        hashmap[target] = j

        return []

另外一个做法可以叫做 2d Kadane's Algorithm.

一道类似的题，Maximum Sub Subrectangle, 这里有视频教程 https://www.youtube.com/watch?v=yCQN096CwWM

思想一样的，就是把数组拉片，然后把片压成一维数组。下面是截图：

用 L, R 两个指针把数组拉片，然后压缩成右边那个一维数组，然后在这个数组里面操作。

压缩这个过程貌似是 O(N^2) 的感觉，但是，具体流程里面，右边这个一维数组是逐步更新的，所以 amortized cost 是 O(N)

按照这个思路，写下程序

    def submatrixSum(self, matrix):

        m, n = len(matrix), len(matrix[0])

        for lo in xrange(m):               # 上面的图切片是竖着切，这个程序是横着切
            for hi in xrange(lo, m):
                if lo == hi:
                    oneD = matrix[lo]      # oneD 就是上图那个一维数组，起始行的话直接拷贝
                else:
                    oneD = map(sum, zip(oneD, matrix[hi]))  # 如果不是起始行，需要加上本行

                prefixsum = 0                     # prefix sum 是对一维数组的prefix sum
                hashmap = {0 : -1}                # 下面几行只对这个一维数组进行操作
                for i, n in enumerate(oneD):      # 完全就是 one D subarray sum = 0 的那题
                    prefixsum += n
                    if prefixsum in hashmap:
                        j = hashmap[prefixsum]
                        return [(lo, j + 1), (hi, i)]
                    else:
                        hashmap[prefixsum] = i

        return []

两个程序的时间复杂度都是O(N^3)。九章那个方法借用了一个2维数组，所以空间复杂度较大。不过解释起来稍微容易点。

这个网页也讲这题： http://www.cnblogs.com/grandyang/p/5814131.html