BinarySearch 0487 Largest Square Matrix with Same Value

Problem statement

https://binarysearch.com/problems/Largest-Square-Matrix-with-Same-Value/

Solution

Similar to Leetcode 0221 Maximal Square, here dp(i, j) again is the size of largest square with left upper corner in (i, j).

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 i < 0 or j < 0: return 0
            if len(set([M[i][j], M[i][j-1], M[i-1][j], M[i-1][j-1]])) != 1: return 1
            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)))