Leetcode 1628 Solution

This article provides solution to leetcode question 1628 (count-submatrices-with-all-ones)
Categories:
Tags:
Access this page by simply typing in "lcs 1628" in your browser address bar if you have bunnylol configured.

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