leetcode

commit 2026181648f9a947f6ba9cac7f8497579010d278
parent 5ea66938849e5a07d6d7c9d20256421d43680457
Author: Jack Sangdahl <jack@pngu.org>
Date:   Sat, 26 Oct 2024 18:12:39 -0600

1277. count square submatricies with all ones

Diffstat:
A
count_square_submatrices_ones.c
 | 
40
++++++++++++++++++++++++++++++++++++++++
A
count_square_submatrices_ones.py
 | 
26
++++++++++++++++++++++++++

2 files changed, 66 insertions(+), 0 deletions(-)
diff --git a/count_square_submatrices_ones.c b/count_square_submatrices_ones.c
@@ -0,0 +1,40 @@
+// 1277. Count Square Submatrices with All Ones
+#include "leetcode.h"
+
+/*
+ * given an 'm * n' matrix of ones and zeros, return how many square submatrices
+ * have all ones.
+ */
+
+int countSquares(int **matrix, int matrixSize, int *matrixColSize) {
+  if (!matrix || !matrixSize || !matrixColSize || !*matrixColSize)
+    return 0;
+  int rows = matrixSize, cols = *matrixColSize;
+  int dp[rows][cols];
+  for (int i = 0; i < rows; i++)
+    dp[i][0] = matrix[i][0];
+  for (int i = 0; i < cols; i++)
+    dp[0][i] = matrix[0][i];
+  for (int i = 1; i < rows; i++)
+    for (int j = 1; j < rows; j++)
+      dp[i][j] = matrix[i][j] == 1
+                     ? fmin(dp[i - 1][j], fmin(dp[i][j - 1], dp[i - 1][j - 1]))
+                     : 0;
+  int cnt = 0;
+  for (int i = 0; i < rows; i++)
+    for (int j = 0; j < cols; j++)
+      cnt += dp[i][j];
+  return cnt;
+}
+
+int main() {
+  int m1i[3][4] = {{0, 1, 1, 1}, {1, 1, 1, 1}, {0, 1, 1, 1}},
+      m2i[3][3] = {{1, 0, 1}, {1, 1, 0}, {1, 1, 0}};
+  struct two_d_arr m1, m2;
+  two_d_arr_init(&m1, 4, 3, m1i);
+  two_d_arr_init(&m2, 3, 3, m2i);
+  printf("%d\n", countSquares(m1.arr, m1.row_size, m2.col_size)); // expect: 15
+  printf("%d\n", countSquares(m2.arr, m2.row_size, m2.col_size)); // expect: 7
+  two_d_arr_free(&m1);
+  two_d_arr_free(&m2);
+}
diff --git a/count_square_submatrices_ones.py b/count_square_submatrices_ones.py
@@ -0,0 +1,26 @@
+# 1277. Count Square Submatrices with All Ones
+
+"""
+given an 'm * n' matrix of ones and zeros, return how many square submatrices
+have all ones.
+"""
+
+
+class Solution(object):
+    def countSquares(self, matrix):
+        """
+        :type matrix: List[List[int]]
+        :rtype: int
+        """
+        for i in range(1, len(matrix)):
+            for j in range(1, len(matrix[0])):
+                matrix[i][j] *= (
+                    min(matrix[i - 1][j], matrix[i][j - 1], matrix[i - 1][j - 1]) + 1
+                )
+        return sum(map(sum, matrix))
+
+
+if __name__ == "__main__":
+    obj = Solution()
+    print(obj.countSquares(matrix=[[0, 1, 1, 1], [1, 1, 1, 1], [0, 1, 1, 1]]))
+    print(obj.countSquares(matrix=[[1, 0, 1], [1, 1, 0], [1, 1, 0]]))