aboutsummaryrefslogtreecommitdiff
path: root/count_submatrices_all_ones.py
diff options
context:
space:
mode:
authorJack Sangdahl <[email protected]>2025-08-20 20:48:55 -0600
committerJack Sangdahl <[email protected]>2025-08-20 20:48:55 -0600
commit4d218d1ca8008396494b307b54560167f18ae0f6 (patch)
tree7b7ded0f8c80036fc03d7ad7ef679635af3a076e /count_submatrices_all_ones.py
parent567f9c64e8224d9e3d899f81004adbb1db0c2b22 (diff)
downloadleetcode-4d218d1ca8008396494b307b54560167f18ae0f6.tar.gz
leetcode-4d218d1ca8008396494b307b54560167f18ae0f6.zip
1504. count submatrices with all ones
Diffstat (limited to 'count_submatrices_all_ones.py')
-rw-r--r--count_submatrices_all_ones.py37
1 files changed, 37 insertions, 0 deletions
diff --git a/count_submatrices_all_ones.py b/count_submatrices_all_ones.py
new file mode 100644
index 0000000..e022235
--- /dev/null
+++ b/count_submatrices_all_ones.py
@@ -0,0 +1,37 @@
+# 1504. Count Submatrices With All Ones
+
+"""
+given an 'm x n' binary matrix 'mat', return the number of submatrices that
+have all ones.
+"""
+
+
+class Solution(object):
+ def numSubmat(self, mat):
+ """
+ :type mat: List[List[int]]
+ :rtype: int
+ """
+ n, m = len(mat), len(mat[0])
+ dp, ans = [0] * m, 0
+ for i in range(n):
+ for j in range(m):
+ dp[j] = dp[j] + 1 if mat[i][j] else 0
+ total, st = [0] * m, []
+ for j in range(m):
+ while st and dp[st[-1]] >= dp[j]:
+ st.pop()
+ if st:
+ curr = st[-1]
+ total[j] = total[curr] + dp[j] * (j - curr)
+ else:
+ total[j] = dp[j] * (j + 1)
+ st.append(j)
+ ans += total[j]
+ return ans
+
+
+if __name__ == "__main__":
+ obj = Solution()
+ print(obj.numSubmat(mat=[[1, 0, 1], [1, 1, 0], [1, 1, 0]]))
+ print(obj.numSubmat(mat=[[0, 1, 1, 0], [0, 1, 1, 1], [1, 1, 1, 0]]))