diff options
Diffstat (limited to 'count_square_submatrices_ones.py')
-rw-r--r-- | count_square_submatrices_ones.py | 26 |
1 files changed, 26 insertions, 0 deletions
diff --git a/count_square_submatrices_ones.py b/count_square_submatrices_ones.py new file mode 100644 index 0000000..399a741 --- /dev/null +++ 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]])) |