Problem statement

https://binarysearch.com/problems/Social-Distancing-2/

Solution

Variation of Leetcode 0221. Maximal Square: here we need to find the biggest square of size q and then return (q + 1)//2.

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] == 1: 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
        
        q =  max(dp(i, j) for i, j in product(range(n), range(m)))
        return (q+1)//2