Given a 2D grid of 0s and 1s, return the number of elements in the largest square subgrid that has all 1s on its border, or 0 if such a subgrid doesn't exist in the grid.
 
Example 1:
Input: grid = [[1,1,1],[1,0,1],[1,1,1]]
Output: 9

Example 2:
Input: grid = [[1,1,0,0]]
Output: 1

 
Constraints:

1 <= grid.length <= 100
1 <= grid[0].length <= 100
grid[i][j] is 0 or 1

Difficulty: interview

Starter code:

class Solution:
    def largest1BorderedSquare(self, grid: List[List[int]]) -> int:
        

Solutions:
class Solution:
    def largest1BorderedSquare(self, grid: List[List[int]]) -> int:
        rows = len(grid)
        cols = len(grid[0])
        memo = [[0 for j in range(cols)] for i in range(rows)]
        ans = 0
        
        if grid[0][0] == 1:
            memo[0][0] = (1,1)
            ans = 1
        else:
            memo[0][0] = (0,0)
        
        for i in range(1,rows):
            if grid[i][0] == 0:
                memo[i][0] = (0,0)
            else:
                memo[i][0] = (memo[i-1][0][0]+1,1)
                ans = 1
        
        for j in range(1,cols):
            if grid[0][j] == 0:
                memo[0][j] = (0,0)
            else:
                memo[0][j] = (1,memo[0][j-1][1]+1)
                ans = 1
            
        for i in range(1,rows):
            for j in range(1,cols):
                if grid[i][j] == 0:
                    memo[i][j] = (0,0)
                else:
                    memo[i][j] = (memo[i-1][j][0]+1, memo[i][j-1][1]+1)
                    ans = 1
        
        for i in range(rows-1,0,-1):
            for j in range(cols-1,0,-1):
                l_min = min(memo[i][j][0],memo[i][j][1])
                
                while l_min>ans:
                    if memo[i][j-l_min+1][0]>=l_min and memo[i-l_min+1][j][1]>=l_min:
                        ans = l_min
                    l_min -= 1
        return ans*ans


class Solution:
    def largest1BorderedSquare(self, grid: List[List[int]]) -> int:
        maxVal = 0
        m = len(grid)
        n = len(grid[0])
        hor = [[0]*n for i in range(m)]
        ver = [[0]*n for i in range(m)]
        
        for i in range(m):
            for j in range(n):
                if grid[i][j] == 1:
                    hor[i][j] = 1 if j == 0 else 1 + hor[i][j-1]
                    ver[i][j] = 1 if i == 0 else 1 + ver[i-1][j]
        
        for i in range(m-1,-1,-1):
            for j in range(n-1, -1, -1):
                small = min(hor[i][j], ver[i][j])
                while small > maxVal:
                    if ver[i][j-small+1] >= small and hor[i-small+1][j] >= small:
                        maxVal = small
                    small -= 1
        return maxVal**2

class Solution:
    def largest1BorderedSquare(self, grid: List[List[int]]) -> int:
        ans = 0
        m, n = len(grid), len(grid[0])
        h = [row[:] for row in grid]
        v = [row[:] for row in grid]
        for row in range(m):
            for col in range(1, n):
                if h[row][col] != 0:
                    h[row][col] += h[row][col-1]
        for col in range(n):
            for row in range(1, m):
                if v[row][col] != 0:
                    v[row][col] += v[row-1][col]
        for row in range(m):
            for col in range(n):
                curr = grid[row][col]
                if not curr: continue
                side = h[row][col] if h[row][col] < v[row][col] else v[row][col]
                res = 1
                for x in range(side, 0, -1):
                    if v[row][col-x+1] >= x and h[row-x+1][col] >= x:
                        res = x*x
                        break
                if res > ans:
                    ans = res
        return ans

class Solution:
    def largest1BorderedSquare(self, grid: List[List[int]]) -> int:
        if len(grid) == 0 or len(grid[0]) == 0:
            return 0
        dp = [[0] * len(grid[0]) for i in range(len(grid))]
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if i == 0 and j == 0:
                    dp[i][j] = grid[i][j]
                elif i == 0 and j > 0:
                    print(f'i{i}')
                    print(f'j{j}')
                    dp[i][j] = dp[i][j - 1] + grid[i][j]
                elif j == 0 and i > 0:
                    dp[i][j] = dp[i - 1][j] + grid[i][j]
                if i >= 1 and j >= 1:
                    dp[i][j] = dp[i - 1][j] + dp[i][j - 1] - dp [i -1][j - 1] + grid[i][j]
            
                
        res = 0
        print(dp)
        length_range = min(len(grid), len(grid[0]))
        for length in range(length_range):
            for x1 in range(len(grid)- length):
                for y1 in range(len(grid[0]) - length):
                    if x1 == 1 and y1 ==0:
                        print(\"denug\")
                    if (self.getLength(grid, dp, x1, y1, x1 + length, y1) == length + 1 and
                       self.getLength(grid, dp, x1, y1, x1, y1 + length) == length + 1 and
                       self.getLength(grid, dp, x1 + length, y1, x1 + length, y1 + length) == length + 1 and
                       self.getLength(grid, dp, x1, y1 + length, x1 + length, y1 + length) == length + 1):
                        res = (length+1)*(length+1)
        return res               
                    
    def getLength(self, grid, dp, x1, y1, x2, y2):
        area_1 = dp[x1 - 1][y2] if x1 - 1 >= 0 else 0
        area_2 = dp[x2][y1 -1] if y1 -1 >= 0 else 0
        area_3 = dp[x1 -1][y1 - 1] if x1 -1 >= 0 and y1 -1 >= 0 else 0
        return dp[x2][y2] - area_1 - area_2 + area_3

class Solution:
    def largest1BorderedSquare(self, grid: List[List[int]]) -> int:
        if not grid: return 0
        edge, m, n = 0, len(grid), len(grid[0])
        left, top = [[0 for j in range(n+1)] for i in range(m+1)], [[0 for j in range(n+1)] for i in range(m+1)]
        for i in range(m):
            for j in range(n):
                left[i+1][j+1] = (0 if grid[i][j]==0 else 1+left[i+1][j])
                top[i+1][j+1] = (0 if grid[i][j]==0 else 1+top[i][j+1])
                left_ones, top_one = left[i+1][j+1], top[i+1][j+1]
                for length in range(min(left_ones, top_one), edge, -1):
                    if min(left[i+2-length][j+1], top[i+1][j+2-length])  >= length:
                        edge = max(edge,length)
                        break
        return edge**2



class Solution:
    def largest1BorderedSquare(self, grid: List[List[int]]) -> int:
        m = len(grid)
        n = len(grid[0])
        dpdown =[[0] * n for i in range(m)]
        dpright =[[0] * n for i in range(m)]
        for i in range(m):
            cur = 0
            for j in range(n-1,-1,-1):
                if grid[i][j] == 1:
                    cur+=1
                    dpright[i][j] = cur
                else:
                    cur = 0
        for j in range(n):
            cur = 0
            for i in range(m-1,-1,-1):
                if grid[i][j] == 1:
                    cur+=1
                    dpdown[i][j] = cur
                else:
                    cur = 0                    
        res = 0
        for i in range(m):
            for j in range(n):
                for k in range(min(dpright[i][j],dpdown[i][j])):
                    if dpright[i+k][j]>k and dpdown[i][j+k]>k:
                        res = max(k+1,res)
        return res**2

class Solution:
    def largest1BorderedSquare(self, grid: List[List[int]]) -> int:
        ones_up_to_index_rows = [[0] for i in range(len(grid))]
        ones_up_to_index_columns = [[0] for i in range(len(grid[0]))]
        ret = 0
        
        
        for row in range(len(grid)):
            for column in range(len(grid[0])):
                ones_up_to_index_rows[row].append(ones_up_to_index_rows[row][-1] + grid[row][column])
                ones_up_to_index_columns[column].append(ones_up_to_index_columns[column][-1] + grid[row][column])
                

        for row in range(len(grid)):
            column = 0
            
            
            if (len(grid) - row > ret):
                for column in range(len(grid[0])):
                    next_column = column


                    while (next_column < len(grid[0]) and grid[row][next_column] == 1):
                        next_column += 1


                    for i in range(next_column - 1, column - 1, -1):
                        side_length = i - column + 1


                        if (side_length <= ret):
                            break

                        row_index_dp = row + side_length - 1


                        if (row_index_dp < len(grid) and 
                           ones_up_to_index_columns[i][row_index_dp + 1] - ones_up_to_index_columns[i][row] == side_length and
                           ones_up_to_index_rows[row_index_dp][i + 1] - ones_up_to_index_rows[row_index_dp][column] == side_length and
                           ones_up_to_index_columns[column][row_index_dp + 1] - ones_up_to_index_columns[column][row] == side_length):
                            ret = side_length
                            break
            else:
                break
                    
        return ret ** 2  

class Solution:
    def largest1BorderedSquare(self, grid: List[List[int]]) -> int:
        n, m = len(grid), len(grid[0])
        
        lefts = [l[:] for l in grid]
        ups = [l[:] for l in grid]
        
        for i in range(n):
            for j in range(1,m):
                if lefts[i][j]:
                    lefts[i][j]+= lefts[i][j-1]

        for j in range(m):
            for i in range(1,n):
                if ups[i][j]:
                    ups[i][j]+= ups[i-1][j]
        
        rec = 0
        
        for i in range(n):
            for j in range(m):
                if grid[i][j]:
                    rec = max(rec,1)
                    k = min(ups[i][j], lefts[i][j])
                    for r in range(1,k):
                        if lefts[i-r][j]>=r+1 and ups[i][j-r]>=r+1:
                            rec=max(rec, (r+1)**2)
        
        return rec

import numpy as np
class Solution:
    def largest1BorderedSquare(self, grid: List[List[int]]) -> int:
        R, C, count = len(grid), len(grid[0]), 0
        dp=[[[0,0]for _ in range(C +1)]for _ in range(R + 1)]
        for i in range(1,R + 1):
            for j in range(1,C + 1):
                if grid[i - 1][j - 1]==1:
                    dp[i][j][0], dp[i][j][1] = dp[i - 1][j][0] + 1, dp[i][j - 1][1] + 1
                    for k in range(min(dp[i][j][0], dp[i][j][1]), count, -1):
                        if min(dp[i - k + 1][j][1], dp[i][j - k + 1][0]) >= k:
                            count = max(count, k)
                            break
        return count**2

import numpy as np
class Solution:
    def largest1BorderedSquare(self, grid: List[List[int]]) -> int:
        R, C, count = len(grid), len(grid[0]), 0
        dp=[[[0,0]for _ in range(C + 1)]for _ in range(R + 1)]
        for i in range(1,R + 1):
            for j in range(1,C + 1):
                if grid[i - 1][j - 1]==1:
                    dp[i][j][0], dp[i][j][1] = dp[i - 1][j][0] + 1, dp[i][j - 1][1] + 1
                    for k in range(min(dp[i][j][0], dp[i][j][1]), count, -1):
                        if k <= min(dp[i - k + 1][j][1], dp[i][j - k + 1][0]):
                            count = max(count, k)
                            break
        return count**2

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


class Solution:
    import copy
    def largest1BorderedSquare(self, grid: List[List[int]]) -> int:
        ROWS = len(grid)
        COLS = len(grid[0]) if ROWS else 0
        
        right = copy.deepcopy(grid)
        down = copy.deepcopy(grid)
        for r in reversed(range(ROWS)):
            for c in reversed(range(COLS-1)):
                if right[r][c]:
                    right[r][c] += right[r][c+1]
                    
        for r in reversed(range(ROWS-1)):
            for c in reversed(range(COLS)):
                if down[r][c]:
                    down[r][c] += down[r+1][c]
        
        # print(grid)
        # print(down)
        # print(right)
        
        RET = 0
        for r in range(ROWS):
            for c in range(COLS):
                CAP = min(right[r][c], down[r][c])
                for shift in reversed(range(RET, CAP)):
                    if right[r+shift][c] > shift and down[r][c+shift] > shift:
                        RET = shift+1
                        break
        return RET**2

class Solution:
    def largest1BorderedSquare(self, grid: List[List[int]]) -> int:
        #depth search
        N = len(grid)
        M = len(grid[0])
        row = copy.deepcopy(grid)
        col = copy.deepcopy(grid)
        for i in range(N):
            start = M
            prev = 0
            for j in range(M):
                if not prev and grid[i][j]:
                    start = j
                elif prev and not grid[i][j]:
                    row[i][start:j] = list(range(j-start,0,-1))
                    start = M
                prev = grid[i][j]
            row[i][start:M] = list(range(M-start,0,-1))
        for i in range(M):
            start = N
            prev = 0
            for j in range(N):
                if not prev and grid[j][i]:
                    start = j
                elif prev and not grid[j][i]:
                    for k in range(j-start):
                        col[start+k][i] = j-start-k
                    start = N
                prev = grid[j][i]
            for k in range(N-start):
                col[start+k][i] = N-start-k
        maxS = 0
        for i in range(N):
            for j in range(M):
                mS = min(row[i][j], col[i][j])
                for k in range(mS, 0, -1):
                    if k <= maxS:
                        break
                    if row[i+k-1][j] >= k and col[i][j+k-1] >= k:
                        maxS = k
        return maxS*maxS


class Solution:
    def largest1BorderedSquare(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        left = [[0 for j in range(n)] for i in range(m)]
        right = [[0 for j in range(n)] for i in range(m)]
        top = [[0 for j in range(n)] for i in range(m)]
        bottom = [[0 for j in range(n)] for i in range(m)]
        for i in range(m):
            for j in range(n):
                if grid[i][j]:
                    if i:
                        top[i][j] = top[i - 1][j] + 1
                    else:
                        top[i][j] = 1
                    if j:
                        left[i][j] = left[i][j - 1] + 1
                    else:
                        left[i][j] = 1
        for i in range(m - 1, -1, -1):
            for j in range(n - 1, -1, -1):
                if grid[i][j]:
                    if i == m - 1:
                        bottom[i][j] = 1
                    else:
                        bottom[i][j] = bottom[i + 1][j] + 1
                    if j == n - 1:
                        right[i][j] = 1
                    else:
                        right[i][j] = right[i][j + 1] + 1
        res = 0
        for i in range(m):
            for j in range(n):
                if grid[i][j]:
                    res = max(res, 1)
                    side = min(left[i][j], top[i][j])
                    for k in range(side, 0, -1):
                        x, y = i - k + 1, j - k + 1
                        if right[x][y] >= k and bottom[x][y] >= k:
                            res = max(res, k ** 2)
                            break
        return res

class Solution:
    def largest1BorderedSquare(self, grid: List[List[int]]) -> int:
        
        n = len(grid)
        m = len(grid[0])
        
        up = [[0] * m for _ in range(n)]
        left = [[0] * m for _ in range(n)]
        
        for i in range(n):
            for j in range(m):
                if grid[i][j] == 1:
                    up[i][j] = 1 + up[i-1][j] if i > 0 else 1
                    left[i][j] = 1 + left[i][j-1] if j > 0 else 1
        
        max_len = 0
        for i in range(n-1, -1, -1):
            for j in range(m-1, -1, -1):
                if grid[i][j] == 1:
                    length = min(up[i][j], left[i][j])
                    for k in range(length-1, -1, -1):
                        if up[i][j-k] >= k+1 and left[i-k][j] >= k+1:
                            max_len = max(max_len, k+1)
        return max_len * max_len

class Solution:
    def largest1BorderedSquare(self, grid: List[List[int]]) -> int:
        m = len(grid)
        n = len(grid[0])
        x = min(m, n)
        
        right = [[0 for i in range(n)] for j in range(m)]
        down = [[0 for i in range(n)] for j in range(m)]
        
        for i in range(m-1, -1, -1):
            for j in range(n-1, -1, -1):
                if grid[i][j] == 0:
                    continue
                
                right[i][j] = 1 + (right[i][j+1] if j+1 < n else 0)
                down[i][j] = 1 + (down[i+1][j] if i+1 < m else 0)
                
        for l in range(x, 0, -1):
            for i in range(0, m-l+1):
                for j in range(0, n-l+1):
                    if right[i][j] >= l and down[i][j] >= l and right[i+l-1][j] >= l and down[i][j+l-1] >= l:
                        return l * l
        return 0

class Solution:
    def getLeftandTopOnes(self, grid: List[List[int]]):
        leftGrid = [[0] * len(grid[0]) for i in range(len(grid))]
        topGrid = [[0] * len(grid[0]) for i in range(len(grid))]
                
        i = 0
        while (i < len(grid)):
            j = 0
            while (j < len(grid[0])):
                if (i > 0):
                    if (grid[i-1][j] == 1):
                        topGrid[i][j] = topGrid[i-1][j] + 1
                    elif (grid[i-1][j] == 0):
                        topGrid[i][j] = 0
                if (j > 0):
                    if (grid[i][j-1] == 1):
                        leftGrid[i][j] = leftGrid[i][j-1] + 1
                    elif (grid[i][j-1] == 0):
                        leftGrid[i][j] = 0
                j += 1
            i += 1
        return (leftGrid, topGrid)

    
    def getRightandDownOnes(self, grid: List[List[int]]):
        rightGrid = [[0] * len(grid[0]) for i in range(len(grid))]
        downGrid = [[0] * len(grid[0]) for i in range(len(grid))]
        
        i = len(grid) - 1
        while (i >= 0):
            j = len(grid[0]) - 1
            while (j >= 0):
                if (i < len(grid) - 1):
                    if (grid[i+1][j] == 1):
                        downGrid[i][j] = downGrid[i+1][j] + 1
                    elif (grid[i+1][j] == 0):
                        downGrid[i][j] = 0
                if (j < len(grid[0]) - 1):
                    if (grid[i][j+1] == 1):
                        rightGrid[i][j] = rightGrid[i][j+1] + 1
                    elif (grid[i][j+1] == 0):
                        rightGrid[i][j] = 0
                j -= 1
            i -= 1
        return (rightGrid, downGrid)            
           
    def largest1BorderedSquare(self, grid: List[List[int]]) -> int:
        leftOnes, topOnes = self.getLeftandTopOnes(grid)
        
        print(leftOnes)
        print(topOnes)
        
        rightOnes, downOnes = self.getRightandDownOnes(grid)
        
        print(rightOnes)
        print(downOnes)
        
        maxBorder = 0
        i = 0
        seenOne = False
        while (i < len(grid)):
            j = 0
            while (j < len(grid[0])):
                if (grid[i][j] == 1):
                    seenOne = True
                    length = min(topOnes[i][j], leftOnes[i][j])
                    
                    while (length >= 0):
                        if (i - length < 0 or j - length < 0):
                            length -= 1
                            continue
                            
                        if (length == 0):
                            break
                            
                        if (topOnes[i][j-length] >= length and 
                             leftOnes[i-length][j] >= length):
                            break
                        length -= 1
                    maxBorder = max(maxBorder, length)
                j += 1
            i += 1
        
        if (not seenOne):
            return 0
        else:
            return (maxBorder + 1) ** 2


class Solution:
    class Tup:
        def __init__(self, u, l):
            self.u = u
            self.l = l
        def __str__(self):
            return f\"({self.u}, {self.l})\"
    
    def largest1BorderedSquare(self, grid: List[List[int]]) -> int:
        yl = len(grid)
        xl = len(grid[0])
        mem = []
        for y in range(0, yl):
            for x in range(0, xl):
                if x == 0:
                    mem.append([])
                row = mem[y]
                if grid[y][x] == 0:
                    row.append((0,0))
                    continue
                u = grid[y][x] if y == 0 else mem[y - 1][x][0] + 1
                l = grid[y][x] if x == 0 else mem[y][x - 1][1] + 1
                row.append((u, l))
        ml = 0
        print(mem)
        for y in range(0, yl):
            for x in range(0, xl):
                for l in range(0, min(mem[y][x])):
                    if mem[y - l][x][1] >= l + 1 and mem[y][x - l][0] >= l + 1:
                        ml = max(ml, l + 1)
        return ml * ml
                
        

class Solution:
    def largest1BorderedSquare(self, grid: List[List[int]]) -> int:
        m = len(grid)
        n = len(grid[0]) if m > 0 else 0
        
        up = [[0]*n for _ in range(m)]
        left = [[0]*n for _ in range(m)]
        down = [[0]*n for _ in range(m)]
        right = [[0]*n for _ in range(m)]
        
        for i in range(m):
            for j in range(n):
                if grid[i][j] == 1:
                    up[i][j] = 1 + (up[i-1][j] if i > 0 else 0)
                    left[i][j] = 1 + (left[i][j-1] if j > 0 else 0)
        for i in range(m-1, -1, -1):
            for j in range(n-1, -1, -1):
                if grid[i][j] == 1:
                    down[i][j] = 1 + (down[i+1][j] if i+1<m else 0)
                    right[i][j] = 1 + (right[i][j+1] if j+1<n else 0)
        
        print(up)
        print(left)
        print(down)
        print(right)
        
        ans = -1
        for i in range(m):
            for j in range(n):
                min_1 = min(up[i][j], left[i][j])
                for k in range(min_1):
                    if min(down[i-k][j-k], right[i-k][j-k]) >= k:
                        ans = max(ans, k)
        
        return (ans+1)**2


class Solution:
    def largest1BorderedSquare(self, grid: List[List[int]]) -> int:
        rows = len(grid)
        cols = len(grid[0])
        table = [[(0, 0) for _ in range(cols)] for _ in range(rows)]

        for i in range(rows):
            for j in range(cols):
                if grid[i][j] == 1:
                    hor = 1 if j == 0 else table[i][j-1][0] + 1
                    ver = 1 if i == 0 else table[i-1][j][1] + 1

                    table[i][j] = (hor, ver)

        # for i in table:
        #     print(i)

        ans = float('-inf')

        for i in reversed(range(rows)):
            for j in reversed(range(cols)):
                if table[i][j] != (0, 0):
                    min_ = min(table[i][j])
                    while min_ > ans:
                        up = i - min_ + 1
                        left = j - min_ + 1
                        if table[i][left][1] >= min_ and table[up][j][0] >= min_ and min_ > ans:
                            ans = min_
                        min_ -= 1

        return ans * ans if ans != float('-inf') else 0

class Solution:
    def largest1BorderedSquare(self, grid: List[List[int]]) -> int:
        iMax = len(grid)
        jMax = len(grid[0])
        
        table = [[[0, 0] for j in range(jMax+1)] for i in range(iMax+1)]
        
        ans = 0
        
        for i in range(1, iMax+1):
            for j in range(1, jMax+1):
                if grid[i-1][j-1] == 1:
                    table[i][j][0] = table[i-1][j][0]+ 1
                    table[i][j][1] = table[i][j-1][1] + 1
                for k in range(min(table[i][j]), 0, -1):
                    if min(table[i-k+1][j][1], table[i][j-k+1][0]) >= k:
                        ans = max(ans, k)
                        break
        return ans*ans

class Solution:
    def largest1BorderedSquare(self, grid: List[List[int]]) -> int:
        
        r, c = len(grid), len(grid[0])
        dp = [[[0, 0] for i in range(c + 1)] for j in range(r + 1)]
        for i in range(r):
            for j in range(c):
                if grid[i][j] == 1:
                    dp[i + 1][j + 1][0] = dp[i][j + 1][0] + 1 #hor
                    dp[i + 1][j + 1][1] = dp[i + 1][j][1] + 1 #ver
        
        ans = 0
        # print(dp)
        for i in range(r - 1, -1 , -1):
            for j in range(c - 1, -1 , -1):
                poss_length = min(dp[i + 1][j + 1])
                while poss_length > ans:
                    if dp[i + 1][j - poss_length + 2][0] >= poss_length and dp[i - poss_length + 2][j + 1][1] >= poss_length:
                        ans = poss_length
                        
                    poss_length -= 1
            
        return ans ** 2

class Solution:
    def largest1BorderedSquare(self, grid: List[List[int]]) -> int:
        n, m = len(grid), len(grid[0])
        max = 0
        hor = [[0] * m for _ in range(n)]
        ver = [[0] * m for _ in range(n)]
        for i in range(n):
            for j in range(m):
                if grid[i][j] == 1:
                    hor[i][j] = hor[i][j-1] + 1 if j > 0 else 1
                    ver[i][j] = ver[i-1][j] + 1 if i > 0 else 1
        
        for i in range(n-1, -1, -1):
            for j in range(m-1, -1, -1):
                small = min(ver[i][j], hor[i][j])
                while small > max:
                    if hor[i-small+1][j] >= small and ver[i][j-small+1] >= small:
                        max = small
                        break
                    small -= 1
        return max**2


class Solution:
    def largest1BorderedSquare(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        left_reach = [row[:] for row in grid]
        up_reach = [row[:] for row in grid]
        for i in range(m):
            for j in range(n):
                if grid[i][j]:
                    if j > 0:
                        left_reach[i][j] = left_reach[i][j - 1] + 1
                    if i > 0:
                        up_reach[i][j] = up_reach[i - 1][j] + 1
        
        for size in range(min(m, n), 0, -1):
            for i in range(m - size + 1):
                for j in range(n - size + 1):
                    if left_reach[i][j + size - 1] >= size and left_reach[i + size - 1][j + size - 1] >= size \\
                    and up_reach[i + size - 1][j] >= size and up_reach[i + size - 1][j + size - 1] >= size:
                        return size * size
        return 0



#         m, n = len(grid), len(grid[0])
#         left_reach = [[0] * n for _ in range(m)]
#         up_reach = [[0] * n for _ in range(m)]
#         for i in range(m):
#             ones = 0
#             for j, num in enumerate(grid[i]):
#                 if num:
#                     ones += 1
#                 else:
#                     ones = 0
#                 left_reach[i][j] = ones
#             ones = 0
        
#         for j in range(n):
#             ones = 0
#             for i in range(m):
#                 if grid[i][j]:
#                     ones += 1
#                 else:
#                     ones = 0
#                 up_reach[i][j] = ones
                
#         for size in range(min(m, n), 0, -1):
#             for i in range(m - size + 1):
#                 for j in range(n - size + 1):
#                     if left_reach[i][j + size - 1] >= size and left_reach[i + size - 1][j + size - 1] >= size \\
#                     and up_reach[i + size - 1][j] >= size and up_reach[i + size - 1][j + size - 1] >= size:
#                         return size * size
#         return 0
        
        
        
#         m, n = len(grid), len(grid[0])
#         left_reach = [[0] * n for _ in range(m)]
#         right_reach = [[0] * n for _ in range(m)]
#         up_reach = [[0] * n for _ in range(m)]
#         down_reach = [[0] * n for _ in range(m)]
#         for i in range(m):
#             ones = 0
#             for j, num in enumerate(grid[i]):
#                 if num:
#                     ones += 1
#                 else:
#                     ones = 0
#                 left_reach[i][j] = ones
#             ones = 0
#             for j in range(n - 1, -1, -1):
#                 if grid[i][j]:
#                     ones += 1
#                 else:
#                     ones = 0
#                 right_reach[i][j] = ones
        
#         for j in range(n):
#             ones = 0
#             for i in range(m):
#                 if grid[i][j]:
#                     ones += 1
#                 else:
#                     ones = 0
#                 up_reach[i][j] = ones
#             ones = 0
#             for i in range(m - 1, -1, -1):
#                 if grid[i][j]:
#                     ones += 1
#                 else:
#                     ones = 0
#                 down_reach[i][j] = ones
                
#         for size in range(min(m, n), 0, -1):
#             for i in range(m - size + 1):
#                 for j in range(n - size + 1):
#                     if right_reach[i][j] >= size and down_reach[i][j] >= size and left_reach[i + size - 1][j + size - 1] >= size and up_reach[i + size - 1][j + size - 1] >= size:
#                         return size * size
#         return 0
                       

class Solution:
    def largest1BorderedSquare(self, grid: List[List[int]]) -> int:
        entries = []
        res = 0
        for r, row in enumerate(grid):
            for c, item in enumerate(row):
                if item == 0: continue
                if c == 0: res = 1
                else:
                    grid[r][c] += grid[r][c-1]
                    entries.append((r, c))
        rows = len(grid)
        for r, c in entries:
            for length in range(grid[r][c], 0, -1):
                if r + length - 1 >= rows\\
                    or grid[r+length-1][c] < length\\
                    or c - length + 1 < 0\\
                    or any(grid[i][c] < 1 or grid[i][c-length+1] < 1\\
                        for i in range(r + 1, r + length - 1)): continue
                res = max(res, length * length)
                break
        return res

import itertools as it


class Solution:
    def largest1BorderedSquare(self, grid: List[List[int]]) -> int:
        if not grid or not grid[0]:
            return 0
        nrows = len(grid)
        ncols = len(grid[0])
        cum_rows = [
            list(it.accumulate(grid[row], initial=0))
            for row in range(nrows)
        ]
        cum_cols = [
            list(it.accumulate((grid[row][col] for row in range(nrows)), initial=0))
            for col in range(ncols)
        ]
        ans = 0
        for row1, col1 in it.product(range(nrows), range(ncols)):
            if grid[row1][col1] == 0:
                continue
            side = 0
            while row1 + side < nrows and col1 + side < ncols and grid[row1 + side][col1] == 1 and grid[row1][col1 + side] == 1:
                row2 = row1 + side
                col2 = col1 + side
                if (
                    cum_cols[col2][row2 + 1] - cum_cols[col2][row1] == side + 1
                    and cum_rows[row2][col2 + 1] - cum_rows[row2][col1] == side + 1
                ):
                    ans = max(ans, (side + 1) ** 2)
                side += 1
        return ans

import itertools as it


class Solution:
    def largest1BorderedSquare(self, grid: List[List[int]]) -> int:
        if not grid or not grid[0]:
            return 0
        nrows = len(grid)
        ncols = len(grid[0])
        cum_rows = [
            list(it.accumulate(grid[row], initial=0))
            for row in range(nrows)
        ]
        cum_cols = [
            list(it.accumulate((grid[row][col] for row in range(nrows)), initial=0))
            for col in range(ncols)
        ]
        ans = 0
        for row1, col1 in it.product(range(nrows), range(ncols)):
            side = 0
            while row1 + side < nrows and col1 + side < ncols and grid[row1 + side][col1] == 1 and grid[row1][col1 + side] == 1:
                row2 = row1 + side
                col2 = col1 + side
                if (
                    cum_cols[col2][row2 + 1] - cum_cols[col2][row1] == side + 1
                    and cum_rows[row2][col2 + 1] - cum_rows[row2][col1] == side + 1
                ):
                    ans = max(ans, (side + 1) ** 2)
                side += 1
        return ans

class Solution:
        
    def largest1BorderedSquare(self, grid: List[List[int]]) -> int:
        n = len(grid)
        if n == 0: return 0
        m = len(grid[0])
        
        top = Solution.fill_top(grid, n, m)
        left = Solution.fill_left(grid, n, m)
        bottom = Solution.fill_bottom(grid, n, m)
        right = Solution.fill_right(grid, n, m)
        
        def top_left(i, j):
            return min(top[i][j], left[i][j])
        
        def bottom_right(i, j):
            return min(bottom[i][j], right[i][j])
        
        square = 0
        
        for i in range(n):
            for j in range(m):
                sliding = top_left(i, j)
                
                for s in range(sliding-1, -1, -1):
                    k = i - s
                    l = j - s
                    if bottom_right(k, l) >= (s + 1):
                        square = max(square, s + 1)
                        
        return square ** 2
                        
        
    @staticmethod
    def empty(n, m):
        return [[0] * m for _ in range(n)]
    
    @staticmethod
    def fill_top(grid, n, m):
        top = Solution.empty(n, m)
        
        for i in range(n):
            if i == 0:
                for j in range(m):
                    top[0][j] = grid[0][j]
            else:
                for j in range(m):
                    top[i][j] = top[i-1][j] + 1 if grid[i][j] == 1 else 0
        return top
    
    @staticmethod
    def fill_left(grid, n, m):
        left = Solution.empty(n, m)
        
        for j in range(m):
            if j == 0:
                for i in range(n):
                    left[i][0] = grid[i][0]
            else:
                for i in range(n):
                    left[i][j] = left[i][j - 1] + 1 if grid[i][j] == 1 else 0
        return left
        
    @staticmethod    
    def fill_bottom(grid, n, m):
        bottom = Solution.empty(n, m)
        
        for i in range(n-1, -1, -1):
            if i == n - 1:
                for j in range(m):
                    bottom[n-1][j] = grid[n-1][j]
            else:
                for j in range(m):
                    bottom[i][j] = bottom[i + 1][j] + 1 if grid[i][j] == 1 else 0
        return bottom
    
    @staticmethod
    def fill_right(grid, n, m):
        right = Solution.empty(n, m)
            
        for j in range(m-1, -1, -1):
            if j == m-1:
                for i in range(n):
                    right[i][m-1] = grid[i][m-1]
            else:
                for i in range(n):
                    right[i][j] = right[i][j + 1] + 1 if grid[i][j] == 1 else 0
        return right
                        
    
        


class Solution:
    def largest1BorderedSquare(self, grid: List[List[int]]) -> int:
        
        m, n = len(grid), len(grid[0])
        
        LU = [[(0,0)]*(n+1) for _ in range(m+1)]
        for r in range(m):
            for c in range(n):
                if grid[r][c] > 0:
                    LU[r+1][c+1] = (1 + LU[r+1][c][0], 1 + LU[r][c+1][1])
        
        area = 0
        for r in range(m):
            for c in range(n):
                x, y = LU[r+1][c+1]
                for i in range(min(x,y)-1,-1,-1):
                    if min(LU[r+1-i][c+1][0], LU[r+1][c+1-i][1]) >= i+1:
                        area = max(area, (i+1)**2)
        
        return area
                    
        


class Solution:
    
    def checkForSquare(self, grid: List[List[int]], i: int, j: int, squareLen: int) -> bool:
        maxRowBound = i + squareLen - 1
        maxColBound = j + squareLen - 1
        #print(\"Checking for square at \" + str(maxRowBound) + \",\" + str(maxColBound))
        #print(\"Square_len: \" + str(squareLen))
        if (self.accessGrid(grid, maxRowBound, maxColBound) == 1):
            # check bottom line
            k = maxColBound
            while (k != j and self.accessGrid(grid, maxRowBound, k) == 1):
                k -= 1    
            if (k != j):
                return False
            
            # check rightmost line
            s = maxRowBound
            while (s != i and self.accessGrid(grid, s, maxColBound) == 1):
                s -= 1    
            if (s == i):
                #print(\"Found square at \" + str(maxRowBound) + \",\" + str(maxColBound))
                #print(\"Square_len: \" + str(squareLen))
                return True
            
        return False
    
    def accessGrid(self, grid: List[List[int]], i: int, j: int) -> int:
        if (i < self.rows and j < self.cols):
            return grid[i][j]
        else:
            return -1
    
    def largest1BorderedSquare(self, grid: List[List[int]]) -> int:
        
        self.rows = len(grid)
        self.cols = len(grid[0])
        
        # brute-force
        
        i = 0
        j = 0
        largest_square = 0
        
        #print(\"Rows: \" + str(self.rows))
        #print(\"Cols: \" + str(self.cols))
        
        while (i < self.rows):
            while (j < self.cols):
                #print(\"Checking \" + str(i) + \",\" + str(j))
                search_increment = 1
                if (grid[i][j] == 1):
                    if (largest_square == 0):
                        largest_square = 1
                    if (j != self.cols - 1):
                        #print(\"Searching for square at \" + str(i) + \",\" + str(j))
                        # Find possible bounds of the square
                        max_col_bound = j
                        max_row_bound = i
                        while (self.accessGrid(grid, i, max_col_bound) == 1):
                            max_col_bound += 1
                        square_len = max_col_bound - j

                        if (square_len > 0):
                            while (self.accessGrid(grid, max_row_bound, j) == 1):
                                max_row_bound += 1

                        square_len = min(square_len, max_row_bound - i)
                        while (square_len ** 2 > largest_square):
                            if (self.checkForSquare(grid, i, j, square_len)):
                                largest_square = square_len ** 2
                                search_increment = square_len - 1
                            else:
                                square_len -= 1
                j += search_increment

                # If the largest square is bigger than the rest of the column
                # search space, we can move to the next row
                remaining_search_space = (self.cols - j) ** 2
                if (largest_square >= remaining_search_space):
                    break
            i += 1
            j = 0
            # If the largest square is bigger than the rest of the
            # search space, we can return
            remaining_search_space = (self.rows - i) ** 2
            if (largest_square >= remaining_search_space):
                return largest_square
        
        return largest_square
                        
                        
                        
               
                
        
        


class Solution:
    def largest1BorderedSquare(self, grid: List[List[int]]) -> int:
        
        horizon = [[0]*len(grid[0]) for _ in range(len(grid))]
        vertical = [[0]*len(grid[0]) for _ in range(len(grid))]
        
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if grid[i][j] == 1:
                    horizon[i][j] = horizon[i][j-1] + 1

        for i in range(len(grid[0])):
            for j in range(len(grid)):
                if grid[j][i] == 1:
                    vertical[j][i] = vertical[j-1][i] + 1
                    
        res = 0
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                
                s = min(horizon[i][j], vertical[i][j])
                for k in range(s, 0, -1):
                    if horizon[i-k+1][j] >= k and vertical[i][j-k+1] >= k:
                        res = max(res, k)
                        break
                        
                
        return res*res
                


class Solution:
    def largest1BorderedSquare(self, grid: List[List[int]]) -> int:
        rows = len(grid)
        cols = len(grid[0])
        dp = [[None] * cols for _ in range(rows)]
        maxSize = 0
        for i in range(rows):
            for j in range(cols):
                x, y = 0, 0
                if grid[i][j] == 1:
                    if i > 0 and dp[i-1][j]:
                        x = dp[i-1][j][0] + 1
                    if j > 0 and dp[i][j-1]:
                        y = dp[i][j-1][1] + 1
                    dp[i][j] = (x,y)
                    sqlen = min(x,y)
                    while sqlen >= maxSize:
                        left = dp[i][j-sqlen]
                        up = dp[i-sqlen][j]
                        if left[0] >= sqlen and up[1] >= sqlen:
                            maxSize = sqlen + 1
                        sqlen -= 1
        return maxSize * maxSize
                    
                    


class Solution:
    def largest1BorderedSquare(self, grid: List[List[int]]) -> int:
        
        dp = [[None] * len(grid[0]) for _ in range(len(grid))]
        dp[0][0] = (1,1) if grid[0][0] == 1 else (0,0)
        
        for r in range(len(grid)):
            for c in range(len(grid[0])):
                
                if r == 0 and c == 0: continue
                #handle first row
                elif r == 0:
                    if grid[0][c] == 1:
                        newR = 1
                        newC = 1 + dp[0][c-1][1]
                        dp[r][c] = (newR,newC)
                    else:
                        dp[r][c] = (0,0)
                
                elif c == 0:
                    if grid[r][0] == 1:
                        newR = 1 + dp[r-1][0][0]
                        newC = 1
                        dp[r][c] = (newR,newC)
                    else:
                        dp[r][c] = (0,0)
                else:
                    if grid[r][c] == 1:
                        newR = 1 + dp[r-1][c][0]
                        newC = 1+ dp[r][c-1][1]
                        dp[r][c] = (newR,newC)
                    else:
                        dp[r][c] = (0,0)
        
        # print(dp)
        maxGrid = 0
        # now lets iterate from bottom right to upper left
        for r in range(len(grid)-1,-1,-1):
            for c in range(len(grid[0])-1,-1,-1):
                
                minSpan = min(dp[r][c][0],dp[r][c][1])
                if minSpan == 0: continue
                # print('r',r,'c',c,'minSpan',minSpan)
                # we need to loop through min span
                for span in range(minSpan,-1,-1):
                    #check left dp span and see if its row == minSpan
                    cSpanLeft = c-span+1
                    rSpanUp = r-span+1
                    # print(r,c,cSpanLeft,rSpanUp)
                    # print('dp[r][cSpanLeft][0]',dp[r][cSpanLeft][0],'dp[rSpanUp][c][1]',dp[rSpanUp][c][1] )
                    if dp[r][cSpanLeft][0] >= span and dp[rSpanUp][c][1] >= span:
                        # print('maxis', minSpan)
                        maxGrid = max(maxGrid,span**2)
                        break
        
        return maxGrid


class Solution:
    def largest1BorderedSquare(self, grid: List[List[int]]) -> int:
        m = len(grid)
        n = len(grid[0])
        horizon = [row[:] for row in grid]
        for i in range(m):
            for j in range(1,n):
                if horizon[i][j] != 0:
                    horizon[i][j] = horizon[i][j-1] + 1
        vertical = [row[:] for row in grid]
        for i in range(n):
            for j in range(1,m):
                if vertical[j][i] != 0:
                    vertical[j][i] = vertical[j-1][i] + 1
            
        result = 0
        for i in range(m):
            for j in range(n):
                if grid[i][j] == 1:
                    side = min(horizon[i][j], vertical[i][j])
                    eval = 0
                    for dis in range(side,0,-1):
                        if horizon[i-dis+1][j] >= dis and vertical[i][j-dis+1] >= dis:
                            eval = dis * dis
                            break
                    if eval > result:
                        result = eval
        return result


class Solution:
    def largest1BorderedSquare(self, grid: List[List[int]]) -> int:
        ylen, xlen = len(grid), len(grid[0])
        rights = [[0 for i in range(xlen)] for j in range(ylen)]
        downs = [[0 for i in range(xlen)] for j in range(ylen)]
        for y in range(ylen-1, -1, -1):
            for x in range(xlen-1, -1, -1):
                if y < ylen-1 and grid[y+1][x] == 1:
                    downs[y][x] = downs[y+1][x] + 1
                if x < xlen-1 and grid[y][x+1] == 1:
                    rights[y][x] = rights[y][x+1] + 1
        ans = 0
        for y,row in enumerate(grid):
            for x,val in enumerate(row):
                if val == 1:
                    ans = max(ans, 1)
                    offset = 1
                    while y+offset < ylen and x+offset < xlen:
                        cury, curx = y + offset, x + offset
                        if grid[cury][x] == 1 and grid[y][curx] == 1:
                            if rights[cury][x] >= offset and downs[y][curx] >= offset:
                                ans = max(ans, 1+offset)
                        else:
                            break
                        offset += 1
        return ans**2

class Solution:
    def largest1BorderedSquare(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        result = 0
        for i in range(m):
            for j in range(n):
                if grid[i][j] == 0:
                    continue
                l = (grid[i][j - 1] & 0xff if j else 0) + 1
                u = ((grid[i - 1][j] >> 8) & 0xff if i else 0) + 1
                grid[i][j] = u << 8 | l
                s = 1
                for k in reversed(list(range(min(l, u)))):
                    if (grid[i][j - k] >> 8) > k and (grid[i - k][j] & 0xff) > k:
                        s = k + 1
                        break
                result = max(result, s * s)
        return result


class Solution:
    def largest1BorderedSquare(self, grid: List[List[int]]) -> int:
        left = []
        right = []
        up = []
        down = []
        for i in range(len(grid)):
            left.append([0] * len(grid[0]))
            right.append([0] * len(grid[0]))
            up.append([0] * len(grid[0]))
            down.append([0] * len(grid[0]))
        for i in range(len(grid)):
            left[i][0] = grid[i][0]
            right[i][-1] = grid[i][-1]
            for j in range(1, len(grid[0])):
                if grid[i][j] == 1:
                    left[i][j] = left[i][j-1] + 1
                if grid[i][len(grid[0]) - j - 1] == 1:
                    right[i][len(grid[0]) - j - 1] = right[i][len(grid[0]) - j] + 1
        for j in range(len(grid[0])):
            up[0][j] = grid[0][j]
            down[-1][j] = grid[-1][j]
            for i in range(1, len(grid)):
                if grid[i][j] == 1:
                    up[i][j] = up[i-1][j] + 1
                if grid[len(grid) - 1 - i][j] == 1:
                    down[len(grid) - 1 - i][j] = down[len(grid) - i][j] + 1

        for i in range(len(grid)):
            for j in range(len(grid[0])):
                left[i][j] = min(left[i][j], up[i][j])
                right[i][j] = min(right[i][j], down[i][j])
        maxium = 0
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if right[i][j] != 0:
                    k = 1
                    while k <= right[i][j] and i + k - 1 < len(grid) and j + k - 1 < len(grid[0]):
                        if left[i+k-1][j+k-1] >= k:
                            maxium = max(maxium, k)
                        k += 1
        return maxium ** 2

class Solution:
    
    def largest1BorderedSquare(self, grid: List[List[int]]) -> int:
        
        def checkSquare(i, j, k):
            
            for ind in range(k+1):
                if grid[i][j+ind] == 0 or grid[i+ind][j] == 0:
                    return 1
            
            for ind in range(k+1):
                if grid[i+ind][k+j] == 0 or grid[i+k][j+ind] ==0:
                    return 2
                
            return 0
            
        n = len(grid)
        m = len(grid[0])
        max_ = 0
        min_ = 0

        for i in range(n):
            
            if max_ > (n-i-1)**2:
                break
            for j in range(m):
                
                if grid[i][j] == 1:
                    bound = min(n-i, m-j)
                
                    if max_ > (bound-1)**2:
                        break
                    else:
                        min_=1
                        for k in range(1, bound):
                            result = checkSquare(i,j, k)
                            if result == 0:
                                max_ = max(max_, (k+1)**2)
                            elif result == 1:
                                break
                              
        return max(max_, min_)


class Solution:
    def largest1BorderedSquare(self, grid: List[List[int]]) -> int:
        if not grid or not grid[0]:
            return 0
        
        rows, cols = len(grid), len(grid[0])
        ans = 0
        
        for row in range(rows):
            for col in range(cols):
                ans = max(ans, self.dfs(grid,row,col))
        
        return ans
        
    def dfs(self, grid, i, j):
        rows, cols = len(grid), len(grid[0])
        # make sure the curr element is a 1
        
        if not grid[i][j]:
            return 0
        
        last = 0
        for offset in (range(min(rows-i,cols-j))):
            # make sure no 0s
            if not grid[i][j+offset] or not grid[i+offset][j]:
                return (last+1)*(last+1)
            
            if self.isValid(grid, [i,j+offset], [i+offset,j]):
                last = offset
            
        return (last+1)*(last+1)
    
    def isValid(self, grid, right, down):
        while True:
            if not grid[right[0]][right[1]] or not grid[down[0]][down[1]]:
                return False
            if right == down:
                return True
            right[0] += 1
            down[1] += 1
            
\"\"\"
[[1,1,1],[1,1,0],[1,1,1],[0,1,1],[1,1,1]]
        1       1       1
        1       1       0
        1       1       1
        0       1       1
        1       1       1
\"\"\"
        

class Solution:
    
    def largest1BorderedSquare(self, grid: List[List[int]]) -> int:
        
        def checkSquare(i, j, k):
            
            for ind in range(k+1):
                if grid[i][j+ind] == 0 or grid[i+ind][j] == 0:
                    return 1
            
            for ind in range(k+1):
                if grid[i+ind][k+j] == 0 or grid[i+k][j+ind] ==0:
                    return 2
                
            return 0
            
        n = len(grid)
        m = len(grid[0])
        max_ = 0
        min_ = 0

        for i in range(n):
            
            if max_ > (n-i-1)**2:
                break
                
            for j in range(m):
                
                if grid[i][j] == 1:
                    bound = min(n-i, m-j)
                
                    if max_ > (bound-1)**2:
                        break
                    else:
                        min_=1
                        for k in range(1, bound):
                            result = checkSquare(i,j, k)
                            if result == 0:
                                max_ = max(max_, (k+1)**2)
                            elif result == 1:
                                break
                              
        return max(max_, min_)


class Solution:
    def largest1BorderedSquare(self, grid: List[List[int]]) -> int:
        dp1=[[0]*len(grid[0]) for i in range(len(grid))]
        dp2=[[0]*len(grid[0]) for i in range(len(grid))]
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if grid[i][j]==0:
                    continue
                dp1[i][j]=(dp1[i-1][j] if i-1>=0 else 0)+1
                dp2[i][j]=(dp2[i][j-1] if j-1>=0 else 0)+1
        ret=0
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if grid[i][j]==0:
                    continue
                for k in range(min(dp1[i][j],dp2[i][j]),0,-1):
                    if k<=min(dp2[i-k+1][j],dp1[i][j-k+1]):
                        ret=max(ret,k**2)
                        break
        return ret
                    


class Solution:
    
    def largest1BorderedSquare(self, grid: List[List[int]]) -> int:
        
        def checkSquare(i, j, k):
            
            for ind in range(k+1):
                if grid[i][j+ind] == 0 or grid[i+ind][j] == 0:
                    return 1
            
            for ind in range(k+1):
                if grid[i+ind][k+j] == 0 or grid[i+k][j+ind] ==0:
                    return 2
                
            return 0
            
        n = len(grid)
        m = len(grid[0])
        max_ = 0
        min_ = 0

        for i in range(n):
            for j in range(m):
                
                if grid[i][j] == 1:
                    bound = min(n-i, m-j)
                
                    if max_ > (bound-1)**2:
                        continue
                        
                    else:
                        min_=1

                        for k in range(1, bound):
                            result = checkSquare(i,j, k)
                            if result == 0:
                                max_ = max(max_, (k+1)**2)
                            elif result == 1:
                                break
                              
        return max(max_, min_)


class Solution:
    def largest1BorderedSquare(self, A: List[List[int]]) -> int:
        n, m = len(A), len(A[0])
        V, H = [[0] * m for _ in range(n)], [[0] * m for _ in range(n)]
        for col in range(m):
            for row in range(n):
                if row == 0:
                    V[row][col] = A[row][col]
                else:
                    V[row][col] = 0 if A[row][col] == 0 else V[row - 1][col] + 1
        
        for row in range(n):
            for col in range(m):
                if col == 0:
                    H[row][col] = A[row][col]
                else:
                    H[row][col] = 0 if A[row][col] == 0 else H[row][col - 1] + 1
        
        res = 0
        for row in range(n):
            for col in range(m):
                small = min(H[row][col], V[row][col])
                while small > res:
                    if V[row][col - small + 1] >= small and H[row - small + 1][col] >= small:
                        res = small
                        break
                    small -= 1
        
        return res * res


class Solution:
    
    def largest1BorderedSquare(self, grid: List[List[int]]) -> int:
        
        def checkSquare(i, j, k):
            
            for ind in range(k+1):
                if grid[i][j+ind] == 0 or grid[i+ind][j] == 0:
                    return 1
            
            for ind in range(k+1):
                if grid[i+ind][k+j] == 0 or grid[i+k][j+ind] ==0:
                    return 2
                
            return 0
            
        n = len(grid)
        m = len(grid[0])
        max_ = 0
        min_ = 0

        for i in range(n):
            for j in range(m):
                bound = min(n-i, m-j)
                
                if max_ > (bound-1)**2:
                    continue
                
                elif grid[i][j] == 1:
                    min_=1

                    for k in range(1, bound):
                        result = checkSquare(i,j, k)
                        if result == 0:
                            max_ = max(max_, (k+1)**2)
                        elif result == 1:
                            break
                              
        return max(max_, min_)


class Solution:
    def largest1BorderedSquare(self, grid: List[List[int]]) -> int:
        nrow, ncol = len(grid), len(grid[0])
        up, left = [], []
        for _ in range(nrow):
            up.append([0] * ncol)
            left.append([0] * ncol)
        for r in range(nrow):
            for c in range(ncol):
                if grid[r][c] == 1:
                    if c - 1 >= 0:
                        left[r][c] = left[r][c-1] + 1
                    else:
                        left[r][c] = 1
        for c in range(ncol):
            for r in range(nrow):
                if grid[r][c] == 1:
                    if r - 1 >= 0:
                        up[r][c] = up[r-1][c] + 1
                    else:
                        up[r][c] = 1
        # print(left, up)
        
        ret = 0
        for r in range(nrow):
            for c in range(ncol):
                if grid[r][c] == 0: continue
                for dist in range(0, min(r, c)+1):
                    
                    r2, c2 = r - dist, c - dist
                    # print(r, c, dist, r2, c2)
                    if grid[r2][c] == 0 or grid[r][c2] == 0:
                        break
                    if left[r2][c] >= dist + 1 and up[r][c2] >= dist + 1:
                        ret = max(ret, dist+1)
                        
        return ret ** 2
                
                    
                    
                
                
        
        
        


class Solution:
    def largest1BorderedSquare(self, grid: List[List[int]]) -> int:
        
        down =  [[0 for i in range(len(grid[0]))] for j in range(len(grid))]
        up = [[0 for i in range(len(grid[0]))] for j in range(len(grid))]
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if i == 0:
                    down[i][j] = grid[i][j]
                else:
                    if grid[i][j] == 0:
                        continue
                    down[i][j] = down[i-1][j] + grid[i][j]
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if j == 0:
                    up[i][j] = grid[i][j]
                else:
                    if grid[i][j] == 0:
                        continue
                    up[i][j] = up[i][j-1] + grid[i][j]
        
        ans = 0
        mx = 0
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                toSubtract = min(down[i][j], up[i][j])
                while(toSubtract > mx):
                    nj = j - toSubtract + 1
                    ni = i - toSubtract + 1
                    if 0 <= ni < len(grid) and 0 <= nj < len(grid[0]) and down[i][nj] >= toSubtract and up[ni][j] >= toSubtract:
                        ans = max(ans, toSubtract)
                    toSubtract -= 1
        
        return ans*ans

class Solution:
    
    def checkForSquare(self, grid: List[List[int]], i: int, j: int, squareLen: int) -> bool:
        maxRowBound = i + squareLen - 1
        maxColBound = j + squareLen - 1
        print(\"Checking for square at \" + str(maxRowBound) + \",\" + str(maxColBound))
        print(\"Square_len: \" + str(squareLen))
        if (self.accessGrid(grid, maxRowBound, maxColBound) == 1):
            # check bottom line
            k = maxColBound
            while (k != j and self.accessGrid(grid, maxRowBound, k) == 1):
                k -= 1    
            if (k != j):
                return False
            
            # check rightmost line
            s = maxRowBound
            while (s != i and self.accessGrid(grid, s, maxColBound) == 1):
                s -= 1    
            if (s == i):
                print(\"Found square at \" + str(maxRowBound) + \",\" + str(maxColBound))
                print(\"Square_len: \" + str(squareLen))
                return True
            
        return False
    
    def accessGrid(self, grid: List[List[int]], i: int, j: int) -> int:
        if (i < self.rows and j < self.cols):
            return grid[i][j]
        else:
            return -1
    
    def largest1BorderedSquare(self, grid: List[List[int]]) -> int:
        
        self.rows = len(grid)
        self.cols = len(grid[0])
        
        # brute-force
        
        i = 0
        j = 0
        largest_square = 0
        
        #print(\"Rows: \" + str(self.rows))
        #print(\"Cols: \" + str(self.cols))
        
        while (i < self.rows):
            while (j < self.cols):
                #print(\"Checking \" + str(i) + \",\" + str(j))
                search_increment = 1
                if (grid[i][j] == 1):
                    if (largest_square == 0):
                        largest_square = 1
                    if (j != self.cols - 1):
                        #print(\"Searching for square at \" + str(i) + \",\" + str(j))
                        # Find possible bounds of the square
                        max_col_bound = j
                        max_row_bound = i
                        while (self.accessGrid(grid, i, max_col_bound) == 1):
                            max_col_bound += 1
                        square_len = max_col_bound - j

                        if (square_len > 0):
                            while (self.accessGrid(grid, max_row_bound, j) == 1):
                                max_row_bound += 1

                        square_len = min(square_len, max_row_bound - i)
                        while (square_len ** 2 > largest_square):
                            if (self.checkForSquare(grid, i, j, square_len)):
                                largest_square = square_len ** 2
                                search_increment = square_len - 1
                            else:
                                square_len -= 1
                # If the largest square is bigger than the rest of the search
                # space, we can return
                remaining_search_space = max((self.rows - i) ** 2, (self.cols - search_increment) ** 2)
                if (largest_square >= remaining_search_space):
                    return largest_square
                j += search_increment
            i += 1
            j = 0
        
        return largest_square
                        
                        
                        
               
                
        
        
        

class Solution:
    
    def checkForSquare(self, grid: List[List[int]], i: int, j: int, squareLen: int) -> bool:
        maxRowBound = i + squareLen - 1
        maxColBound = j + squareLen - 1
        #print(\"Checking for square at \" + str(maxRowBound) + \",\" + str(maxColBound))
        #print(\"Square_len: \" + str(squareLen))
        if (self.accessGrid(grid, maxRowBound, maxColBound) == 1):
            # check bottom line
            k = maxColBound
            while (k != j and self.accessGrid(grid, maxRowBound, k) == 1):
                k -= 1    
            if (k != j):
                return False
            
            # check rightmost line
            s = maxRowBound
            while (s != i and self.accessGrid(grid, s, maxColBound) == 1):
                s -= 1    
            if (s == i):
                #print(\"Found square at \" + str(maxRowBound) + \",\" + str(maxColBound))
                #print(\"Square_len: \" + str(squareLen))
                return True
            
        return False
    
    def accessGrid(self, grid: List[List[int]], i: int, j: int) -> int:
        if (i < self.rows and j < self.cols):
            return grid[i][j]
        else:
            return -1
    
    def largest1BorderedSquare(self, grid: List[List[int]]) -> int:
        
        self.rows = len(grid)
        self.cols = len(grid[0])
        
        # brute-force
        
        i = 0
        j = 0
        largest_square = 0
        
        #print(\"Rows: \" + str(self.rows))
        #print(\"Cols: \" + str(self.cols))
        
        while (i < self.rows):
            while (j < self.cols):
                #print(\"Checking \" + str(i) + \",\" + str(j))
                search_increment = 1
                if (grid[i][j] == 1):
                    if (largest_square == 0):
                        largest_square = 1
                    if (j != self.cols - 1):
                        #print(\"Searching for square at \" + str(i) + \",\" + str(j))
                        # Find possible bounds of the square
                        max_col_bound = j
                        max_row_bound = i
                        while (self.accessGrid(grid, i, max_col_bound) == 1):
                            max_col_bound += 1
                        square_len = max_col_bound - j

                        if (square_len > 0):
                            while (self.accessGrid(grid, max_row_bound, j) == 1):
                                max_row_bound += 1

                        square_len = min(square_len, max_row_bound - i)
                        while (square_len ** 2 > largest_square):
                            if (self.checkForSquare(grid, i, j, square_len)):
                                largest_square = square_len ** 2
                                search_increment = square_len - 1
                            else:
                                square_len -= 1
                # If the largest square is bigger than the rest of the search
                # space, we can return
                remaining_search_space = max((self.rows - i) ** 2, (self.cols - search_increment) ** 2)
                if (largest_square >= remaining_search_space):
                    return largest_square
                j += search_increment
            i += 1
            j = 0
        
        return largest_square
                        
                        
                        
               
                
        
        


# https://www.acwing.com/solution/LeetCode/content/3171/
# 找出边界全部由 1 组成的最大正方形子网格并返回该子网格中的元素数量
# 枚举每一个子正方形, 第一重循环枚举正方形的长度 length, 第二三重循环枚举左上角的顶点的 x 和 y 坐标位置
# 对于每个正方形, 在线性时间内判断它是否合法
# sum_row[i][j] 表示第 i 行前 j 列数字的和, sum_col[j][i] 表示第 j 列前 i 行的和, 因为是前缀和, 这里的 i 和 j 都从下标 1 开始
# 提前计算出 prefix sum 用于之后在线性复杂度内判断正方形是否合法 (判断四条边的区间和是不是等于 length)
# O(n ∗ m ∗ min(n, m)) time complexity, O(nm) space complexity
class Solution:
    def largest1BorderedSquare(self, grid: List[List[int]]) -> int:
        n, m = len(grid), len(grid[0])
        sum_row, sum_col = [[0] * (m + 1) for _ in range(n + 1)], [[0] * (n + 1) for _ in range(m + 1)]
        for i in range(n + 1):
            for j in range(m + 1):
                sum_row[i][j] = sum_row[i][j - 1] + grid[i - 1][j - 1]
        for j in range(m + 1):
            for i in range(n + 1):
                sum_col[j][i] = sum_col[j][i - 1] + grid[i - 1][j - 1]
        
        for length in range(min(n, m), 0, -1):
            for i in range(n - length + 1):
                for j in range(m - length + 1):
                    x, y = i + length - 1, j + length - 1
                    if sum_row[i + 1][y + 1] - sum_row[i + 1][j] == length \\
                    and sum_row[x + 1][y + 1] - sum_row[x + 1][j] == length \\
                    and sum_col[j + 1][x + 1] - sum_col[j + 1][i] == length \\
                    and sum_col[y + 1][x + 1] - sum_col[y + 1][i] == length:
                        return length * length
        return 0


class Solution:
    
    def largest1BorderedSquare(self, grid: List[List[int]]) -> int:
        
        def checkSquare(i, j, k):
            
            for ind in range(k+1):
                if grid[i][j+ind] == 0 or grid[i+ind][j] == 0:
                    return 1
            
            for ind in range(k+1):
                if grid[i+ind][k+j] == 0 or grid[i+k][j+ind] ==0:
                    return 2
                
            return 0
            
        n = len(grid)
        m = len(grid[0])
        max_ = 0
        min_ = 0

        for i in range(n):
            for j in range(m):
                
                if grid[i][j] == 1:
                    min_=1

                    bound = min(n-i, m-j)

                    for k in range(1, bound):
                        result = checkSquare(i,j, k)
                        if result == 0:
                            max_ = max(max_, (k+1)**2)
                        elif result == 1:
                            break
                              
        return max(max_, min_)


class Solution:
    def largest1BorderedSquare(self, grid: List[List[int]]) -> int:
        
        horizon = [[0]*len(grid[0]) for _ in range(len(grid))]
        vertical = [[0]*len(grid[0]) for _ in range(len(grid))]
        
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if grid[i][j] == 1:
                    horizon[i][j] = horizon[i][j-1] + 1

        for i in range(len(grid[0])):
            for j in range(len(grid)):
                if grid[j][i] == 1:
                    vertical[j][i] = vertical[j-1][i] + 1
                    
        res = 0
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                tmp = 0
                s = min(len(grid)-i, len(grid[0])-j)
                while tmp < s:
                    if horizon[i][j+s-1] >= s and horizon[i+s-1][j+s-1] >= s and vertical[i+s-1][j] >= s and vertical[i+s-1][j+s-1] >= s:
                        tmp = s
                    s -= 1
                res = max(res, tmp)
                
        return res*res
                


class Solution:
    def largest1BorderedSquare(self, grid: List[List[int]]) -> int:
        left_top = []
        for r in range(len(grid)):
            left_top.append([0]*len(grid[0])) 
        right_bottom = []
        for r in range(len(grid)):
            right_bottom.append([0]*len(grid[0]))
        for r in range(len(grid)):
            for c in range(len(grid[0])):
                ans = 0
                while r - ans >= 0 and c - ans >= 0 and grid[r-ans][c] == 1 and grid[r][c-ans] == 1:
                    ans += 1
                left_top[r][c] = ans
        for r in range(len(grid)):
            for c in range(len(grid[0])):
                ans = 0
                while r + ans < len(grid) and c + ans < len(grid[0]) and grid[r+ans][c] == 1 and grid[r][c+ans] == 1:
                    ans += 1
                right_bottom[r][c] = ans                     

        max_len = 0        
        for r in range(len(grid)):
            for c in range(len(grid[0])):
                ans = 0
                for i in range(left_top[r][c]):
                    if right_bottom[r-i][c-i] > i:
                        ans = i + 1
                max_len = max(max_len, ans)
        return max_len**2

class Solution:

    def correct(self, i: int, j: int, n: int, m: int) -> bool:
        return 0 <= i < n and 0 <= j < m

    def largest1BorderedSquare(self, grid: List[List[int]]) -> int:
        n = len(grid)
        m = len(grid[0])
        lu = [[0] * m for i in range(n)]
        rd = [[0] * m for i in range(n)]
        for i in range(n):
            for j in range(m):
                k = 0
                while self.correct(i - k, j, n, m) and self.correct(i, j - k, n, m) \\
                      and grid[i - k][j] == 1 and grid[i][j - k] == 1:
                    k += 1
                lu[i][j] = k
        for i in range(n):
            for j in range(m):
                k = 0
                while self.correct(i + k, j, n, m) and self.correct(i, j + k, n, m) \\
                      and grid[i + k][j] == 1 and grid[i][j + k] == 1:
                    k += 1
                rd[i][j] = k
        res = 0
        for i in range(n):
            for j in range(m):
                for k in range(rd[i][j] - 1, -1, -1):
                    if lu[i + k][j + k] > k:
                        res = max(res, (k + 1) ** 2)
                        break
        return res

class Solution:
    def largest1BorderedSquare(self, grid: List[List[int]]) -> int:
        
        if not grid:
            return 0
        
        
        m = len(grid)
        n = len(grid[0])
        # brute force
        max_len = max(m, n)
        
        row_count = [[grid[i][0]] for i in range(m)]
        for i in range(m):
            for j in range(1, n):
                if grid[i][j]:
                    row_count[i].append(row_count[i][j-1]+1)
                else:
                    row_count[i].append(0)
        
        col_count = [[grid[0][j] for j in range(n)]]
        for i in range(1, m):
            col_count.append([])
            for j in range(n):
                if grid[i][j]:
                    col_count[i].append(col_count[i-1][j]+1)
                else:
                    col_count[i].append(0)
        
        for l in range(max_len, 0, -1):
            for i in range(m-l+1):
                for j in range(n-l+1):
                    if self.find_board(i, j, l, row_count, col_count):
                        return l*l
        return 0
        
        
        
    
    def find_board(self, i, j, l, row_count, col_count):
        if l==1:
            return row_count[i][j] == 1
        
        l = l-1
        #check four coners
        x, y = i+l, j+l
        
        if row_count[i][y] <= l:
            return False
        
        if row_count[x][y] <= l:
            return False
        
        if col_count[x][j] <= l:
            return False
        
        if col_count[x][y] <= l:
            return False
            
        
        return True
        
            
        


class Solution:

    def correct(self, i: int, j: int, n: int, m: int) -> bool:
        return 0 <= i < n and 0 <= j < m

    def largest1BorderedSquare(self, grid: List[List[int]]) -> int:
        n = len(grid)
        m = len(grid[0])
        lu = [[0] * m for i in range(n)]
        rd = [[0] * m for i in range(n)]
        for i in range(n):
            for j in range(m):
                k = 0
                while self.correct(i - k, j, n, m) and self.correct(i, j - k, n, m) \\
                      and grid[i - k][j] == 1 and grid[i][j - k] == 1:
                    k += 1
                lu[i][j] = k
        for i in range(n):
            for j in range(m):
                k = 0
                while self.correct(i + k, j, n, m) and self.correct(i, j + k, n, m) \\
                      and grid[i + k][j] == 1 and grid[i][j + k] == 1:
                    k += 1
                rd[i][j] = k
        res = 0
        for i in range(n):
            for j in range(m):
                for k in range(rd[i][j] - 1, -1, -1):
                    if lu[i + k][j + k] > k:
                        res = max(res, (k + 1) ** 2)
        return res

class Solution:
    def largest1BorderedSquare(self, grid: List[List[int]]) -> int:
        n, m = len(grid), len(grid[0])
        right, below = [([0] * m) for i in range(n)], [([0] * m) for i in range(n)]
        
        for i in range(n):
            for j in range(m):
                if i == 0:
                    below[n-1-i][m-1-j] = grid[n-1-i][m-1-j]
                else:
                    below[n-1-i][m-1-j] = grid[n-1-i][m-1-j] * (1+below[n-i][m-1-j])
                        
                if j == 0:
                    right[n-1-i][m-1-j] = grid[n-1-i][m-1-j]
                else:
                    right[n-1-i][m-1-j] = grid[n-1-i][m-1-j] * (1+right[n-1-i][m-j])
        
        max_s = 0
        
        for i in range(n):
            for j in range(n-i):
                for k in range(m-j):
                    if (below[i][k] >= j+1) & (right[i][k] >= j+1):
                        if (below[i][k+j] >= j+1) & (right[i+j][k] >= j+1):
                            if j+1 > max_s:
                                max_s = j+1
        
        return max_s ** 2

import copy

class Solution:
  def largest1BorderedSquare(self, grid: List[List[int]]) -> int:
    # step1, O(N^2), dp, count the consecutive 1s start at (i, j) to top, left, down, right, (t, l, d, r)
    # step2, O(N^3), straightforward, at (i, j), take (i + k, j + k), for k in range(1, min(d,r)-at-(i,j)), 
    #  see if min(t,l)-at-(i+k, j+k) >= k for k-square, often, k is limited and early break, so the overall
    #  performance is expected to be close to O(N^2) instead of O(N^3).
    m, n = len(grid), len(grid[0])
    # tldr: 4 x m x n
    tldr = [copy.deepcopy(grid) for _ in range(4)]
    for i in range(m):
      for j in range(n):
        if grid[i][j]:
          if i:
            tldr[0][i][j] = tldr[0][i - 1][j] + 1
          if j:
            tldr[1][i][j] = tldr[1][i][j - 1] + 1
    for j in range(n - 1, -1, -1):
      for i in range(m - 1, -1, -1):
        if grid[i][j]:
          if i + 1 < m:
            tldr[2][i][j] = tldr[2][i + 1][j] + 1
          if j + 1 < n:
            tldr[3][i][j] = tldr[3][i][j + 1] + 1
    # diagonal only
    mk = 0
    for i in range(m):
      for j in range(n):
        k0 = 0 if i == 0 or j == 0 else min(tldr[2][i - 1][j - 1], tldr[3][i - 1][j - 1])
        for k in range(min(tldr[2][i][j], tldr[3][i][j]) - 1, k0 - 1, -1):
          if min(tldr[0][i + k][j + k], tldr[1][i + k][j + k]) >= k:
            mk = max(mk, k + 1)
            break
    return mk * mk

class Solution:
    def largest1BorderedSquare(self, grid: List[List[int]]) -> int:
        n = len(grid)
        m = len(grid[0])

        def expand_square(r, c):
            left, top = [r, c], [r, c]
            side = 0
            area = 0
            while left[0] < n and top[1] < m and grid[left[0]][left[1]] == 1 and grid[top[0]][top[1]] == 1:
                valid = True
                for row in range(top[0], left[0] + 1):
                    if grid[row][top[1]] == 0:
                        valid = False
                        break
                for col in range(left[1], top[1] + 1):
                    if grid[left[0]][col] == 0:
                        valid = False
                        break
                if valid:
                    area = (side + 1) ** 2
                top[1] += 1
                left[0] += 1
                side += 1

            return area

        max_area = 0
        for r in range(n):
            for c in range(m):
                max_area = max(max_area, expand_square(r, c))
        return max_area


class Solution:
    def largest1BorderedSquare(self, grid: List[List[int]]) -> int:
        
        horizon = [[0]*len(grid[0]) for _ in range(len(grid))]
        vertical = [[0]*len(grid[0]) for _ in range(len(grid))]
        
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if grid[i][j] == 1:
                    horizon[i][j] = horizon[i][j-1] + 1

        for i in range(len(grid[0])):
            for j in range(len(grid)):
                if grid[j][i] == 1:
                    vertical[j][i] = vertical[j-1][i] + 1
                    
        res = 0
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                s = min(len(grid)-i, len(grid[0])-j)
                for k in range(s):
                    if horizon[i][j+k] >= k+1 and horizon[i+k][j+k] >= k+1 and vertical[i+k][j] >= k+1 and vertical[i+k][j+k] >= k+1:
                        res = max(res, k+1)
                
        return res*res
                


class Solution:
    def getLeftandTopOnes(self, grid: List[List[int]]):
        leftGrid = [[0] * (len(grid[0])+1) for i in range(len(grid)+1)]
        topGrid = [[0] * (len(grid[0])+1) for i in range(len(grid)+1)]
            
        for row in range(1, len(grid)+1):
            for col in range(1, len(grid[0])+1):
                if (grid[row-1][col-1] == 0):
                    continue
                leftGrid[row][col] = leftGrid[row][col-1] + 1
                topGrid[row][col] = topGrid[row-1][col] + 1
        return (leftGrid, topGrid)          
           
    def largest1BorderedSquare(self, grid: List[List[int]]) -> int:
        leftOnes, topOnes = self.getLeftandTopOnes(grid)        
        
        print(leftOnes)
        print(topOnes)
        
        maxBorder = 0
        for row in range(1, len(grid)+1):
            for col in range(1, len(grid[0])+1):
                dist = min(topOnes[row][col], leftOnes[row][col])
                while (dist > 0):
                    if (topOnes[row][col-dist+1] >= dist and leftOnes[row-dist+1][col] >= dist):
                        maxBorder = max(maxBorder, dist*dist)
                        break
                    dist -= 1
        return maxBorder


class Solution:
    def largest1BorderedSquare(self, grid: List[List[int]]) -> int:
        # O(m*n*min(m,n))
        up = [[0 for _ in range(len(grid[0])+1)] for _ in range(len(grid)+1)]
        left = [[0 for _ in range(len(grid[0])+1)] for _ in range(len(grid)+1)]
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                    if grid[i][j]:
                        up[i+1][j+1] = up[i][j+1] + 1
                        left[i+1][j+1] = left[i+1][j] + 1
        maxlen = 0       
        MAXSQ = min(len(grid[0]), len(grid))
        for i in range(len(grid)):
            for j in range(len(grid[0])):   
                for slen in range(maxlen+1, MAXSQ+1):
                    if up[i+1][j+1] >= slen and left[i+1][j+1] >= slen and i+1-(slen-1) > 0 and j+1-(slen-1) > 0 and \\
                            up[i+1][j+1-(slen-1)] >= slen and left[i+1-(slen-1)][j+1] >= slen:

                        maxlen = max(maxlen, slen)
        return maxlen * maxlen
                

class Solution:
    def largest1BorderedSquare(self, grid: List[List[int]]) -> int:
        
        m, n = len(grid), len(grid[0])
        res = 0
        top, left = [a[:] for a in grid], [a[:] for a in grid]
        for i in range(m):
            for j in range(n):
                if grid[i][j]:
                    if i:
                        top[i][j] = top[i-1][j]+1
                    if j:
                        left[i][j] = left[i][j-1]+1
        
        for r in range(min(m,n), 0, -1):
            for i in range(m-r+1):
                for j in range(n-r+1):
                    if min(top[i+r-1][j], top[i+r-1][j+r-1],
                           left[i][j+r-1], left[i+r-1][j+r-1])>=r:
                        return r*r
        return 0
        


class Solution:
    def largest1BorderedSquare(self, A: List[List[int]]) -> int:
        m, n = len(A), len(A[0])
        res = 0
        top, left = [a[:] for a in A], [a[:] for a in A]
        for i in range(m):
            for j in range(n):
                if A[i][j]:
                    if i: top[i][j] = top[i - 1][j] + 1
                    if j: left[i][j] = left[i][j - 1] + 1
        for r in range(min(m, n), 0, -1):
            for i in range(m - r + 1):
                for j in range(n - r + 1):
                    if min(top[i + r - 1][j], top[i + r - 1][j + r - 1], left[i]
                           [j + r - 1], left[i + r - 1][j + r - 1]) >= r:
                        return r * r
        return 0

class Solution:
    def largest1BorderedSquare(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        res = 0
        top, left = [a[:] for a in grid], [a[:] for a in grid]
        for i in range(m):
            for j in range(n):
                if grid[i][j]:
                    if i: top[i][j] = top[i - 1][j] + 1
                    if j: left[i][j] = left[i][j - 1] + 1
        for r in range(min(m, n), 0, -1):
            for i in range(m - r + 1):
                for j in range(n - r + 1):
                    if min(top[i + r - 1][j], top[i + r - 1][j + r - 1], left[i][j + r - 1], left[i + r - 1][j + r - 1]) >= r:
                        return r * r
        return 0

import itertools as it


class Solution:
    def largest1BorderedSquare(self, grid: List[List[int]]) -> int:
        if not grid or not grid[0]:
            return 0
        nrows = len(grid)
        ncols = len(grid[0])
        cum_rows = [
            list(it.accumulate(grid[row], initial=0))
            for row in range(nrows)
        ]
        cum_cols = [
            list(it.accumulate((grid[row][col] for row in range(nrows)), initial=0))
            for col in range(ncols)
        ]
        ans = 0
        for row1, col1 in it.product(range(nrows), range(ncols)):
            if grid[row1][col1] == 0:
                continue
            side = 0
            while row1 + side < nrows and col1 + side < ncols:
                row2 = row1 + side
                col2 = col1 + side
                if (
                    cum_cols[col1][row2 + 1] - cum_cols[col1][row1] == side + 1
                    and cum_cols[col2][row2 + 1] - cum_cols[col2][row1] == side + 1
                    and cum_rows[row1][col2 + 1] - cum_rows[row1][col1] == side + 1
                    and cum_rows[row2][col2 + 1] - cum_rows[row2][col1] == side + 1
                ):
                    ans = max(ans, (side + 1) ** 2)
                side += 1
        return ans

class Solution:
    def largest1BorderedSquare(self, grid: List[List[int]]) -> int:
        # check discussion
        # Time: O(N^3)
        # Step1: Need two auxillary matrix to record the number of consecutive 1s on the vertical and horizontal direction
        # Step2: check every possible candidate width from min(m, n) to 1
        
        m, n = len(grid), len(grid[0])
        # Key: initialize them to SAME as grid, because value=0 got length 0, value=1 got length 1
        horizontal_len = [row[:] for row in grid]
        vertical_len = [row[:] for row in grid]
        # calculate maximum length of one in two directions
        for i in range(m):
            for j in range(n):
                if grid[i][j] > 0:
                    if i > 0:
                        vertical_len[i][j] = vertical_len[i - 1][j] + 1
                    if j > 0:
                        horizontal_len[i][j] = horizontal_len[i][j - 1] + 1
        
        for width in range(min(m, n), 0, -1):
            for i in range(m - width + 1):
                for j in range(n - width + 1):
                    # Key: check the length on the 4 vertex in the horizontal/vertical direction, which indicate the maximum length
                    valid_width = min(horizontal_len[i][j + width - 1],
                                     horizontal_len[i + width - 1][j + width - 1],
                                     vertical_len[i + width - 1][j],
                                     vertical_len[i + width - 1][j + width - 1])
                    # Key: NOT return valid_width, because \"width\" is the currently checking width, while valid_width MIGHT misleading. grid=[[0,1,0,1],[1,1,1,1],[1,1,0,1],[1,1,1,1]], i=1,j=1, valid_width is 4, but TRUE valid width is ONLY 3. If TRUR width is 4, we SHOULD find it when i=0,j=0
                    if valid_width >= width:
                        return width ** 2
        return 0


class Solution:
    def largest1BorderedSquare(self, A):
            m, n = len(A), len(A[0])
            res = 0
            top, left = [a[:] for a in A], [a[:] for a in A]
            for i in range(m):
                for j in range(n):
                    if A[i][j]:
                        if i: top[i][j] = top[i - 1][j] + 1
                        if j: left[i][j] = left[i][j - 1] + 1
            for r in range(min(m, n), 0, -1):
                for i in range(m - r + 1):
                    for j in range(n - r + 1):
                        if min(top[i + r - 1][j], top[i + r - 1][j + r - 1], left[i]
                               [j + r - 1], left[i + r - 1][j + r - 1]) >= r:
                            return r * r
            return 0

class Solution:
    def largest1BorderedSquare(self, A: List[List[int]]) -> int:
        m=len(A)
        n=len(A[0])
        
        top=[a[:] for a in A]
        left=[a[:] for a in A]
        
        for i in range(m):
            for j in range(n):
                if A[i][j]:
                    if i :
                        top[i][j]=top[i-1][j]+1
                    if j:
                        left[i][j]=left[i][j-1]+1
        

        for r in range(min(m,n),0,-1):
            for  i in range(m-r+1):
                for j in range(n-r+1):
                    
                    if min(top[i + r - 1][j], top[i + r - 1][j + r - 1], left[i]
                           [j + r - 1], left[i + r - 1][j + r - 1]) >= r:
                        return r * r
        return 0


class Solution:
    def largest1BorderedSquare(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        res = 0
        top, left = [a[:] for a in grid], [a[:] for a in grid]
        for i in range(m):
            for j in range(n):
                if grid[i][j] == 1:
                    if i: top[i][j] = top[i - 1][j] + 1
                    if j: left[i][j] = left[i][j - 1] + 1
        for r in range(min(m, n), 0, -1):
            for i in range(m - r + 1):
                for j in range(n - r + 1):
                    if min(top[i + r - 1][j], top[i + r - 1][j + r - 1], left[i]
                           [j + r - 1], left[i + r - 1][j + r - 1]) >= r:
                        return r * r
        return 0

class Solution:
    def largest1BorderedSquare(self, grid: List[List[int]]) -> int:
        rows, cols = len(grid), len(grid[0])
        n = min(rows,cols)
        rs = [row[:] for row in grid]
        cs = [row[:] for row in grid]
        for row in range(rows):
            for col in range(cols):
                if grid[row][col]:
                    if row:
                        cs[row][col] = cs[row-1][col] + 1
                    if col:
                        rs[row][col] = rs[row][col-1] + 1
        for size in range(n, 0, -1):
            for row in range(rows-size+1):
                for col in range(cols-size+1):
                    if min(cs[row+size-1][col], cs[row+size-1][col+size-1], rs[row][col+size-1], rs[row+size-1][col+size-1]) >= size:
                        return size*size
        return 0
                    


class Solution:
    def largest1BorderedSquare(self, grid: List[List[int]]) -> int:
        ans = 0
        m, n = len(grid), len(grid[0])
        h = [row[:] for row in grid]
        v = [row[:] for row in grid]
        for row in range(m):
            for col in range(1, n):
                if h[row][col] != 0:
                    h[row][col] += h[row][col-1]
        for col in range(n):
            for row in range(1, m):
                if v[row][col] != 0:
                    v[row][col] += v[row-1][col]
        for row in range(m):
            for col in range(n):
                curr = grid[row][col]
                if not curr: continue
                side = h[row][col] if h[row][col] < v[row][col] else v[row][col]
                res = 1
                for x in range(side, 0, -1): 
                    if v[row][col-x+1] >= x and h[row-x+1][col] >= x: #连续的1要大于边长
                        res = x*x
                        break
                if res > ans:
                    ans = res
        return ans

class Solution:
    def largest1BorderedSquare(self, A):
        m, n = len(A), len(A[0])
        res = 0
        top, left = [a[:] for a in A], [a[:] for a in A]
        for i in range(m):
            for j in range(n):
                if A[i][j]:
                    if i: top[i][j] = top[i - 1][j] + 1
                    if j: left[i][j] = left[i][j - 1] + 1
        for r in range(min(m, n), 0, -1):
            for i in range(m - r + 1):
                for j in range(n - r + 1):
                    if min(top[i + r - 1][j], top[i + r - 1][j + r - 1], left[i]
                           [j + r - 1], left[i + r - 1][j + r - 1]) >= r:
                        return r * r
        return 0

class Solution:
    def largest1BorderedSquare(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        
        left = [a[:] for a in grid]
        top = [a[:] for a in grid]
        
        for i in range(m):
            for j in range(n):
                if grid[i][j]:
                    left[i][j] = left[i][j-1]+1 if j else 1
                    top[i][j] = top[i-1][j]+1 if i else 1
        
        for l in range(min(m,n), 0, -1):
            for i in range(m-l+1):
                for j in range(n-l+1):
                    if min(top[i+l-1][j], top[i+l-1][j+l-1],
                          left[i][j+l-1], left[i+l-1][j+l-1]) >= l:
                        return l * l
                    
        return 0

from math import floor
from math import ceil
from math import sqrt
from collections import deque
import numpy
from _collections import deque
#from _ast import Num # LC doesn't like this
from heapq import *
from typing import List
import random

MOD = int(1e9 + 7)
BASE = 256

from math import floor
from math import ceil
from math import sqrt
from collections import deque
import numpy
from _collections import deque
#from _ast import Num # LC doesn't like this
from heapq import *
from typing import List
import random

MOD = int(1e9 + 7)
BASE = 256
\"\"\"
startSI
nextSI
totalUsed

curEnd = si + (cnt - 1) * (m+1)
if curEnd >= nextSI:
    nextSI = curEnd + 1

if startSI

totalUsed += cnt

123123144 -> 143124123 -> 12312412455
14312412355


\"\"\"

from math import floor
from math import ceil
from math import sqrt
from collections import deque
import numpy
from _collections import deque
#from _ast import Num # LC doesn't like this
from heapq import *
from typing import List
import random

MOD = int(1e9 + 7)
BASE = 256

from math import floor
from math import ceil
from math import sqrt
from collections import deque
import numpy
from _collections import deque
#from _ast import Num # LC doesn't like this
from heapq import *

from typing import List
import random

MOD = int(1e9 + 7)
BASE = 256
\"\"\"
possible[weight][N] = possible[N - weight][N - 1], or 
\"\"\"


class Solution:

    def largest1BorderedSquare(self, grid: List[List[int]]) -> int:
        N = len(grid)
        M = len(grid[0])
        left0i = [[-1 for _ in range(M)] for _ in range(N)]
        down0i = [[-1 for _ in range(M)] for _ in range(N)]

        for i in range(N):
            for j in range(M):
                if grid[i][j]:
                    if j:
                        left0i[i][j] = left0i[i][j - 1]
                else:
                    left0i[i][j] = j


#        print(left0i)

        for j in range(M):
            for i in range(N):
                if grid[i][j]:
                    if i:
                        down0i[i][j] = down0i[i - 1][j]
                else:
                    down0i[i][j] = i

        for l in range(min(M, N), 0, -1):
            for i in range(l - 1, N):
                for j in range(l - 1, M):
                    bottom = j - left0i[i][j]
                    top = j - left0i[i - l + 1][j]
                    left = i - down0i[i][j - l + 1]
                    size = min(bottom, i - down0i[i][j], left, top)
                    if size >= l:
                        return l * l
        return 0

class Solution:
    def largest1BorderedSquare(self, grid: List[List[int]]) -> int:
        # O(m*n*min(m,n))
        up = [[0 for _ in range(len(grid[0])+1)] for _ in range(len(grid)+1)]
        left = [[0 for _ in range(len(grid[0])+1)] for _ in range(len(grid)+1)]
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                    if grid[i][j]:
                        up[i+1][j+1] = up[i][j+1] + 1
                        left[i+1][j+1] = left[i+1][j] + 1
        res = 0       
        for d in up:
            print(d)
        for l in left:
            print(l)
        MAXSQ = min(len(grid[0]), len(grid))
        for i in range(len(grid)):
            for j in range(len(grid[0])):   
                for slen in range(1, MAXSQ+1):
                    if up[i+1][j+1] >= slen and left[i+1][j+1] >= slen and i+1-(slen-1) > 0 and j+1-(slen-1) > 0 and \\
                            up[i+1][j+1-(slen-1)] >= slen and left[i+1-(slen-1)][j+1] >= slen:

                        res = max(res, slen*slen)
                # while i+1-slen > 0 and j+1-slen > 0 and left[i+1-slen][j+1] >= slen and up[i+1][j+1-slen] >= slen:
                #     slen += 1
                    
        return res
                

class Solution:
    def largest1BorderedSquare(self, grid: List[List[int]]) -> int:
        top = [a[:] for a in grid]
        left = [a[:] for a in grid]
        
        m, n = len(grid), len(grid[0])
        for i in range(m):
            for j in range(n):
                if grid[i][j]:
                    if i > 0:
                        top[i][j] = top[i-1][j] + 1
                    if j > 0:
                        left[i][j] = left[i][j-1] + 1
        
        for r in range(min(m,n), 0, -1):
            for i in range(m - r + 1):
                for j in range(n - r + 1):
                    if min(top[i + r - 1][j], top[i + r - 1][j + r - 1], left[i][j + r - 1], left[i + r - 1][j + r - 1]) >= r:
                        return r * r
        
        return 0

class Solution:
    def largest1BorderedSquare(self, grid: List[List[int]]) -> int:
        n=len(grid)
        m=len(grid[0])
        rows=[[0 for j in range(m+1)] for i in range(1+n)] # along rows
        cols=[[0 for j in range(m+1)] for i in range(1+n)] # along cols
        for i in range(1,n+1):
            for j in range(1,m+1):
                rows[i][j]=rows[i][j-1]+grid[i-1][j-1]
                cols[i][j]=cols[i-1][j]+grid[i-1][j-1]
        res = 0
        for i in range(1,n+1):
            for j in range(1,m+1):
                if grid[i-1][j-1]:
                    k=1
                    res=max(res,1)
                    while i+k<=n and j+k<=m:
                        if rows[i][j + k] - rows[i][j - 1] == rows[i + k][j + k] - rows[i + k][j - 1] == cols[i + k][j] - cols[i - 1][j] == cols[i + k][j + k] - cols[i - 1][j + k] == k + 1:
                            res=max(res,(k+1)*(k+1))
                        k+=1
        return res

class Solution:
    def largest1BorderedSquare(self, grid: List[List[int]]) -> int:
        m = len(grid)
        n = len(grid[0])
        sum_row = []
        sum_col = []
        for i in range(m):
            sum_row.append([0]*n)
            sum_col.append([0]*n)
        for i in range(m):
            # print(i)
            sum_row[i][0] = grid[i][0]
            # print(sum_row[i][0], grid[i][0])
            # print(sum_row[0], sum_row[1], sum_row[2])
            for j in range(1, n):
                # print(i, j)
                sum_row[i][j] = sum_row[i][j-1] + grid[i][j]
                # print(sum_row)
        # print(sum_row, 'end') 
        for j in range(n):
            sum_col[0][j] = grid[0][j]
            for i in range(1, m):
                sum_col[i][j] = sum_col[i-1][j] + grid[i][j]
        # print(sum_col, 'end')
        # scan all possible squares
        num_ele = 0
        for i in range(m):
            for j in range(n):
                l = min(i, j)
                # print(i, j, l)
                for k in range(l+1):
                    slen = l-k
                    length = slen + 1
                    # print(i, j, l, k, slen, length)
                    if ((sum_row[i-slen][j] - sum_row[i-slen][j-slen] + grid[i-slen][j-slen]) == length
                    and (sum_row[i][j] - sum_row[i][j-slen] + grid[i][j-slen]) == length
                    and (sum_col[i][j-slen] - sum_col[i-slen][j-slen] + grid[i-slen][j-slen]) == length
                    and (sum_col[i][j] - sum_col[i-slen][j] + grid[i-slen][j]) == length):
                        if length*length > num_ele:
                            num_ele = length*length
                        break
        return num_ele
                    


class Solution:
    def largest1BorderedSquare(self, grid: List[List[int]]) -> int:
        R, C = len(grid), len(grid[0])
        top, left = copy.deepcopy(grid), copy.deepcopy(grid)
        
        # count ones
        for i in range(R):
            for j in range(C):
                if grid[i][j]:
                    if i > 0:
                        top[i][j] = top[i-1][j] + 1
                    if j > 0:
                        left[i][j] = left[i][j-1] + 1
        
        # print(top, left)
        # check for each possible squares
        ans = 0
        for s in range(min(R, C), 0, -1):
            for i in range(R-s+1):
                for j in range(C-s+1):
                   # check top/left one counts for bottom 2 points
                    if min(top[i+s-1][j], top[i+s-1][j+s-1], left[i][j+s-1], left[i+s-1][j+s-1]) >= s:
                        return s * s
        
        return 0


class Solution:
    def largest1BorderedSquare(self, grid: List[List[int]]) -> int:
        row=[0]*len(grid[0])
        dph=[]
        dpv=[]
        for i  in range(len(grid)):
            dph.append([0]*len(grid[0]))
            dpv.append([0]*len(grid[0]))
                       
                       
        
        for i in range(len(grid)):
            if grid[i][0]!=0:
                dph[i][0]=1
            else:
                dph[i][0]=0
                
                
            for j in range(1,len(grid[0])):
                if grid[i][j]!=0:
                    print((i,j))
                    dph[i][j]=dph[i][j-1]+1

                else:
                     
                    dph[i][j]=0
                    
                    
        for j in range(len(grid[0])):
            if grid[0][j]!=0:
                dpv[0][j]=1
            else:
                dpv[0][j]=0
                          
            for i in range(1,len(grid)):
                if grid[i][j]!=0:
                    dpv[i][j]=dpv[i-1][j]+1

                else:
                    dpv[i][j]=0 
       
        print(dpv)
        print(dph)
        

                        
        maxl=0
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if grid[i][j]>0 :
                    startl=min(dpv[i][j],dph[i][j])
                    if startl>maxl:#可能的其实边框长度要大于目前找到的最大边框
                    
                        for k in range(startl,maxl,-1):
                            left=j-k+1
                            top=i-k+1
                            if dpv[i][left]>=k and dph[top][j]>=k:
                                maxl=k
                                break
        return maxl*maxl
            


class Solution:
    def largest1BorderedSquare(self, grid: List[List[int]]) -> int:
        n=len(grid)
        m=len(grid[0])
        row=[[0]*(m+1) for i in range(n+1)]
        col=[[0]*(m+1) for i in range(n+1)]
        for i in range(1,n+1):
            for j in range(1,m+1):
                row[i][j]=row[i][j-1]+grid[i-1][j-1]
                col[i][j]=col[i-1][j]+grid[i-1][j-1]
        res=0
        for i in range(1,n+1):
            for j in range(1,m+1):
                if grid[i-1][j-1]:
                    k=1
                    res=max(res,1)
                    while i+k<=n and j+k<=m:
                        if row[i][j+k]-row[i][j-1]==row[i+k][j+k]-row[i+k][j-1]==col[i+k][j]-col[i-1][j]==col[i+k][j+k]-col[i-1][j+k]==k+1:
                            res=max(res,(k+1)*(k+1))
                        k+=1
        return res
        
        
        
        


class Solution:
    def largest1BorderedSquare(self, grid: List[List[int]]) -> int:
        
        if not grid:
            return 0
        
        
        m = len(grid)
        n = len(grid[0])
        # brute force
        max_len = max(m, n)
        
        for l in range(max_len, 0, -1):
            
            for i in range(m-l+1):
                for j in range(n-l+1):
                    if self.find_board(i, j, l, grid):
                        return l*l
        return 0
        
        
        
    
    def find_board(self, i, j, l, grid):
        if l==1:
            return grid[i][j] == 1
        x1, x2 = i, i+l-1
        for y in range(j, j+l):
            if grid[x1][y] == 0: return False
            if grid[x2][y] == 0: return False
        
        y1, y2 = j, j+l-1
        for x in range(i+1, i+l-1):
            if grid[x][y1] == 0: return False
            if grid[x][y2] == 0: return False
        
        return True
        
            
        


def getArea(x1, y1, x2, y2, dp):
    return dp[x2][y2] - dp[x2][y1-1] - dp[x1-1][y2] + dp[x1-1][y1-1]

class Solution:
    def largest1BorderedSquare(self, grid: List[List[int]]) -> int:
        if len(grid) == 0: return 0
        if len(grid[0]) == 0: return 0
        h, w = len(grid), len(grid[0])
        dp = [[0 for j in range(w+1)] for i in range(h+1)]
        for i in range(1, h+1):
            for j in range(1, w+1):
                dp[i][j] = dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1] + grid[i-1][j-1]
        for l in range(min(h, w), 0, -1):
            for x1 in range(1, h+1):
                for y1 in range(1, w+1):
                    x2 = x1 + l - 1
                    y2 = y1 + l - 1
                    if x2 > h or y2 > w:
                        continue
                    if (getArea(x1, y1, x2, y1, dp) == l \\
                          and getArea(x1, y1, x1, y2, dp) == l \\
                          and getArea(x1, y2, x2, y2, dp) == l
                          and getArea(x2, y1, x2, y2, dp) == l):
                        return l*l
        return 0
                    

class Solution:
    def largest1BorderedSquare(self, grid):
        n=len(grid)
        m=len(grid[0])
        rows=[[0 for j in range(m+1)] for i in range(1+n)] # along rows
        cols=[[0 for j in range(m+1)] for i in range(1+n)] # along cols
        for i in range(1,n+1):
            for j in range(1,m+1):
                rows[i][j]=rows[i][j-1]+grid[i-1][j-1]
                cols[i][j]=cols[i-1][j]+grid[i-1][j-1]
        res = 0
        for i in range(1,n+1):
            for j in range(1,m+1):
                if grid[i-1][j-1]:
                    k=1
                    res=max(res,1)
                    while i+k<=n and j+k<=m:
                        if rows[i][j + k] - rows[i][j - 1] == rows[i + k][j + k] - rows[i + k][j - 1] == cols[i + k][j] - cols[i - 1][j] == cols[i + k][j + k] - cols[i - 1][j + k] == k + 1:
                            res=max(res,(k+1)*(k+1))
                        k+=1
        return res

class Solution:
    # Why would there be a situation that min(top[i + r - 1][j], top[i + r - 1][j + r - 1], left[i][j + r - 1], left[i + r - 1][j + r - 1]) > r???
    def largest1BorderedSquare(self, A):
        m, n = len(A), len(A[0])
        res = 0
        top, left = [a[:] for a in A], [a[:] for a in A]
        for i in range(m):
            for j in range(n):
                if A[i][j]:
                    if i: top[i][j] = top[i - 1][j] + 1
                    if j: left[i][j] = left[i][j - 1] + 1
        for r in range(min(m, n), 0, -1):
            for i in range(m - r + 1):
                for j in range(n - r + 1):
                    if min(top[i + r - 1][j], top[i + r - 1][j + r - 1], left[i]
                           [j + r - 1], left[i + r - 1][j + r - 1]) == r:
                        return r * r
                    elif min(top[i + r - 1][j], top[i + r - 1][j + r - 1], left[i]
                               [j + r - 1], left[i + r - 1][j + r - 1]) > r:
                        print(i,j,r,min(top[i + r - 1][j], top[i + r - 1][j + r - 1], left[i]
                               [j + r - 1], left[i + r - 1][j + r - 1]),m,n)
                        return r * r
        return 0

class Solution:
    
    def largest1BorderedSquare(self, grid: List[List[int]]) -> int:
        
        def checkSquare(i, j, k):
            
            for ind in range(k+1):
                if grid[i][j+ind] == 0 or grid[i+ind][j] == 0 or grid[i+ind][k+j] == 0 or grid[i+k][j+ind] ==0:
                    return False
                
            return True
            
        n = len(grid)
        m = len(grid[0])
        max_ = 0
        min_ = 0

        for i in range(n):
            for j in range(m):
                
                if grid[i][j] == 1:
                    min_=1
                    
                    
                    bound = min(n-i, m-j)
                    
                    
                    for k in range(1, bound):
                        if checkSquare(i,j, k):
                            max_ = max(max_, (k+1)**2)
                              
        return max(max_, min_)


class Solution:
    
    \"\"\"
    1,1,1
    1,1,1
    1,1,1
    
    \"\"\"
                
                
    
    def largest1BorderedSquare(self, grid: List[List[int]]) -> int:
        
        
        def checkSquare(i, j, k):
            
            for ind in range(k+1):
                if grid[i][j+ind] == 0 or grid[i+ind][j] == 0 or grid[i+ind][k+j] == 0 or grid[i+k][j+ind] ==0:
                    return False
                
            return True
            
        n = len(grid)
        m = len(grid[0])
        max_ = 0


        for i in range(n):
            for j in range(m):
                
                if grid[i][j] == 1:
                    max_ = max(max_, 1)
                    
                    bound = min(n-i, m-j)
                    
                    
                    for k in range(1,bound):
                        if checkSquare(i,j, k):
                            max_ = max(max_, (k+1)**2)
                              
        return max_
            

class Solution:
    def largest1BorderedSquare(self, grid: List[List[int]]) -> int:
        def Check(i,j):
            ans = 1
            Dis = min(m - i, n - j)
            for k in range(max_dis, Dis):
                ok = True
                for h in range(i,i+k+1):
                    if grid[h][j] == 0:
                        ok = False
                        break
                    if grid[h][j+k] == 0:
                        ok = False
                        break
                for h in range(j,j+k+1):
                    if grid[i][h] == 0:
                        ok = False
                        break
                    if grid[i+k][h] == 0:
                        ok = False
                        break
                if ok:
                    ans = max(ans, (k+1) * (k+1))
            return ans
        
        m = len(grid)
        n = len(grid[0])
        max_so_far = 0
        max_dis = 0
        for i in range(m):
            for j in range(n):
                if grid[i][j] == 1 and i + max_dis < m and j + max_dis < n:
                    max_so_far = max(max_so_far, Check(i,j))
                    max_dis = int(math.sqrt(max_so_far))
        return max_so_far