Problem Link

Let dpVer[i][j] := the number of continuous 1’s from grid[0][j-1] to grid[i-1][j-1]

Let dpHor[i][j] := the number of continuous 1’s from grid[i-1][0] to grid[i-1][j-1]

class Solution:
    def largest1BorderedSquare(self, grid: List[List[int]]) -> int:
        M, N = len(grid), len(grid[0])
        dpVer = [[0 for i in range(N+1)] for _ in range(M+1)]
        dpHor = [[0 for i in range(N+1)] for _ in range(M+1)]
        maxLen = 0
        for i in range(1, M+1):
            for j in range(1, N+1):
                if grid[i-1][j-1] == 1:
                    dpVer[i][j] = dpVer[i-1][j] + 1
                    dpHor[i][j] = dpHor[i][j-1] + 1
                    k = min(dpVer[i][j], dpHor[i][j])
                    for kk in range(k, 0, -1):
                        if dpVer[i][j-kk+1] >= kk and dpHor[i-kk+1][j] >= kk:
                            maxLen = max(maxLen, kk)
                            break
        return maxLen * maxLen