Leetcode 1628 Solution

This article provides solution to leetcode question 1628 (count-submatrices-with-all-ones)

https://leetcode.com/problems/count-submatrices-with-all-ones

Solution

class Solution: def numSubmat(self, mat: List[List[int]]) -> int: m = len(mat) n = len(mat[0])
s = [[0 for _ in range(n)] for _ in range(m)] for i in range(m): curr_max = 0 for j in range(n): if mat[i][j] == 1: curr_max += 1 else: curr_max = 0 s[i][j] = curr_max
ans = 0 for i in range(m): for j in range(n): k = i curr_max = n while k >= 0: curr_max = min(curr_max, s[k][j])
ans += curr_max k -= 1 return ans