aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorJack Sangdahl <[email protected]>2025-08-19 21:27:20 -0600
committerJack Sangdahl <[email protected]>2025-08-19 21:27:20 -0600
commit567f9c64e8224d9e3d899f81004adbb1db0c2b22 (patch)
treed590c9a96c26ce9f9e3c6c02b0df7535c8bbe4d9
parent933b3b41aa8f2286e7f2f846925b45c8df15282d (diff)
downloadleetcode-567f9c64e8224d9e3d899f81004adbb1db0c2b22.tar.gz
leetcode-567f9c64e8224d9e3d899f81004adbb1db0c2b22.zip
1277. count square submatricies with all ones
-rw-r--r--count_square_submatrices_ones.c25
-rw-r--r--count_square_submatrices_ones.py2
2 files changed, 8 insertions, 19 deletions
diff --git a/count_square_submatrices_ones.c b/count_square_submatrices_ones.c
index c363997..34c8d51 100644
--- a/count_square_submatrices_ones.c
+++ b/count_square_submatrices_ones.c
@@ -7,24 +7,13 @@
*/
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 ans = 0;
+ for (int i = 0; i < matrixSize; ++i)
+ for (int j = 0; j < matrixColSize[i]; ans += matrix[i][j++])
+ if (matrix[i][j] && i && j)
+ matrix[i][j] += fmin(matrix[i - 1][j - 1],
+ fmin(matrix[i - 1][j], matrix[i][j - 1]));
+ return ans;
}
int main() {
diff --git a/count_square_submatrices_ones.py b/count_square_submatrices_ones.py
index 399a741..1ce43e7 100644
--- a/count_square_submatrices_ones.py
+++ b/count_square_submatrices_ones.py
@@ -14,7 +14,7 @@ class Solution(object):
"""
for i in range(1, len(matrix)):
for j in range(1, len(matrix[0])):
- matrix[i][j] *= (
+ matrix[i][j] += (
min(matrix[i - 1][j], matrix[i][j - 1], matrix[i - 1][j - 1]) + 1
)
return sum(map(sum, matrix))