Largest 1-Bordered Square LeetCode solution in Python

1
# Runtime: 1382 ms (Top 13.45%) | Memory: 15.1 MB (Top 9.94%)
2
class Solution:
3
    def largest1BorderedSquare(self, grid: List[List[int]]) -> int:
4
        m = len(grid)
5
        n = len(grid[0])
6
        dp = [[[grid[i][j]] * 4 for j in range(n)] for i in range(m)]
7
        for i in range(m):
8
            for j in range(n):
9
                if i > 0:
10
                    if grid[i][j] == 1:
11
                        dp[i][j][1] = dp[i - 1][j][1] + 1
12
                if j > 0:
13
                    if grid[i][j] == 1:
14
                        dp[i][j][0] = dp[i][j - 1][0] + 1
15
        for i in range(m - 1, -1, -1):
16
            for j in range(n - 1, -1, -1):
17
                if i < m - 1:
18
                    if grid[i][j] == 1:
19
                        dp[i][j][2] = dp[i + 1][j][2] + 1
20
                if j < n - 1:
21
                    if grid[i][j] == 1:
22
                        dp[i][j][3] = dp[i][j + 1][3] + 1
23
        mside = min(m, n)
24
        for l in range(mside - 1, -1, -1):
25
            for i in range(m - l):
26
                for j in range(n - l):
27
                    if (
28
                        min(
29
                            dp[i][j][2],
30
                            dp[i][j][3],
31
                            dp[i + l][j + l][0],
32
                            dp[i + l][j + l][1],
33
                        )
34
                        >= l + 1
35
                    ):
36
                        return (l + 1) * (l + 1)
37
        return 0