# 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**](https://www.lintcode.com/en/problem/submatrix-sum/#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

```python
    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>

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

![](https://3512182187-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M5svbRfnyIVkzjwObqC%2F-M5swpyiHEcoNNP0nIYk%2F-M5syqUyDI6jweOWlCWM%2FsubmatrixSum.png?generation=1587946418535660\&alt=media)用 L, R 两个指针把数组拉片，然后压缩成右边那个一维数组，然后在这个数组里面操作。

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

按照这个思路，写下程序

```python
    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>


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://loghead.gitbook.io/algorithm-notes/array-matrix-interval-binary-indexed-tree/submatrix-sum.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.