aboutsummaryrefslogtreecommitdiff
path: root/count_submatrices_all_ones.c
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.c
parent567f9c64e8224d9e3d899f81004adbb1db0c2b22 (diff)
downloadleetcode-4d218d1ca8008396494b307b54560167f18ae0f6.tar.gz
leetcode-4d218d1ca8008396494b307b54560167f18ae0f6.zip
1504. count submatrices with all ones
Diffstat (limited to 'count_submatrices_all_ones.c')
-rw-r--r--count_submatrices_all_ones.c44
1 files changed, 44 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);
+}