BinarySearch 0346 Largest Square Submatrix

Problem statement

https://binarysearch.com/problems/Largest-Square-Submatrix/

Solution

Equal to Leetcode 0221 Maximal Square

Complexity

It is O(mn) for time and space.

Code

class Solution:
    def solve(self, M):
        m, n = len(M[0]), len(M)
        @lru_cache(None)
        def dp(i, j):
            if M[i][j] == 0: return 0
            if i < 0 or j < 0: return 0
            return min(dp(i-1, j), dp(i, j-1), dp(i-1, j-1)) + 1
        
        return max(dp(i, j) for i, j in product(range(n), range(m)))**2