aboutsummaryrefslogtreecommitdiff
path: root/num_submatrices_sum_target.py
blob: 7f277f5467fad14810a706bfea6f9ade878f47b4 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
# 1074. Number of Submatrices That Sum to Target
from collections import defaultdict

"""
given a 'matrix' and 'target', return the number of non-empty submatrices
that sum to target. a submatrix 'x1, y1 x2, y2' is the set of all cells
'matrix[x][y]' with 'x1 <= x <= x2' and 'y1 <= y <= y2'. two submatrices are
different if they have some coordinate that is different. for example if x1
!= x1
"""


class Solution(object):
    def numSubmatrixSumTarget(self, matrix, target):
        """
        :type matrix: List[List[int]]
        :type target: int
        :rtype: int
        """
        m, n = len(matrix), len(matrix[0])
        for row in matrix:
            for i in range(n - 1):
                row[i + 1] += row[i]
        ans = 0
        for i in range(n):
            for j in range(i, n):
                c = collections.defaultdict(int)
                curr, c[0] = 0, 1
                for k in range(m):
                    curr += matrix[k][j] - (matrix[k][i - 1] if i > 0 else 0)
                    ans += c[curr - target]
                    c[curr] += 1
        return ans


if __name__ == "__main__":
    obj = Solution()
    print(obj.numSubmatrixSumTarget(matrix=[[0, 1, 0], [1, 1, 1], [0, 1, 0]], target=0))
    print(obj.numSubmatrixSumTarget(matrix=[[1, -1], [-1, 1]], target=0))
    print(obj.numSubmatrixSumTarget(matrix=[[904]], target=0))