LeetCode/1504_Count_Submatrices_With_All_Ones.py at main · AnmolPatel20/LeetCode · GitHub

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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
"""
Given an m x n binary matrix mat, return the number of submatrices that have all ones.


Example 1:


Input: mat = [[1,0,1],[1,1,0],[1,1,0]]
Output: 13
Explanation:
There are 6 rectangles of side 1x1.
There are 2 rectangles of side 1x2.
There are 3 rectangles of side 2x1.
There is 1 rectangle of side 2x2.
There is 1 rectangle of side 3x1.
Total number of rectangles = 6 + 2 + 3 + 1 + 1 = 13.
Example 2:


Input: mat = [[0,1,1,0],[0,1,1,1],[1,1,1,0]]
Output: 24
Explanation:
There are 8 rectangles of side 1x1.
There are 5 rectangles of side 1x2.
There are 2 rectangles of side 1x3.
There are 4 rectangles of side 2x1.
There are 2 rectangles of side 2x2.
There are 2 rectangles of side 3x1.
There is 1 rectangle of side 3x2.
Total number of rectangles = 8 + 5 + 2 + 4 + 2 + 2 + 1 = 24.


Constraints:

1 <= m, n <= 150
mat[i][j] is either 0 or 1.

"""

class Solution:
    def numSubmat(self, mat: list[list[int]]) -> int:
        row, col = len(mat), len(mat[0])
        h = [0] * col
        result = 0
        for i in range(row):
            for j in range(col):
                h[j] = h[j] + 1 if mat[i][j] else 0
            for j in range(col):
                mn, k = h[j], j
                while k >= 0 and mn:
                    mn = min(mn,h[k])
                    result += mn
                    k -= 1
        return result