aboutsummaryrefslogtreecommitdiff
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
parent567f9c64e8224d9e3d899f81004adbb1db0c2b22 (diff)
downloadleetcode-4d218d1ca8008396494b307b54560167f18ae0f6.tar.gz
leetcode-4d218d1ca8008396494b307b54560167f18ae0f6.zip
1504. count submatrices with all ones
-rw-r--r--count_submatrices_all_ones.c44
-rw-r--r--count_submatrices_all_ones.py37
2 files changed, 81 insertions, 0 deletions
diff --git a/count_submatrices_all_ones.c b/count_submatrices_all_ones.c
new file mode 100644
index 0000000..ab9c140
--- /dev/null
+++ b/count_submatrices_all_ones.c
@@ -0,0 +1,44 @@
+// 1504. Count Submatrices With All Ones
+#include "leetcode.h"
+
+/*
+ * given an 'm x n' binary matrix 'mat', return the number of submatrices that
+ * have all ones.
+ */
+
+int numSubmat(int **mat, int matSize, int *matColSize) {
+ int m = matColSize[0], ans = 0;
+ int *dp = (int *)calloc(m, sizeof(int));
+ for (int i = 0; i < matSize; i++) {
+ for (int j = 0; j < m; j++)
+ dp[j] = mat[i][j] ? dp[j] + 1 : 0;
+ int *sum = (int *)calloc(m, sizeof(int));
+ int *stack = (int *)malloc(m * sizeof(int)), top = -1;
+ for (int j = 0; j < m; j++) {
+ while (top >= 0 && dp[stack[top]] >= dp[j])
+ top--;
+ if (top >= 0) {
+ int curr = stack[top];
+ sum[j] = sum[curr] + dp[j] * (j - curr);
+ } else
+ sum[j] = dp[j] * (j + 1);
+ stack[++top] = j;
+ ans += sum[j];
+ }
+ free(sum), free(stack);
+ }
+ free(dp);
+ return ans;
+}
+
+int main() {
+ int m1i[3][3] = {{1, 0, 1}, {1, 1, 0}, {1, 1, 0}},
+ m2i[3][4] = {{0, 1, 1, 0}, {0, 1, 1, 1}, {1, 1, 1, 0}};
+ struct two_d_arr m1, m2;
+ two_d_arr_init(&m1, ARRAY_SIZE(m1i), ARRAY_SIZE(m1i[0]), m1i);
+ two_d_arr_init(&m2, ARRAY_SIZE(m2i), ARRAY_SIZE(m2i[0]), m2i);
+ printf("%d\n", numSubmat(m1.arr, m1.row_size, m1.col_size)); // expect: 13
+ printf("%d\n", numSubmat(m2.arr, m2.row_size, m2.col_size)); // expect: 24
+ two_d_arr_free(&m1);
+ two_d_arr_free(&m2);
+}
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]]))