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

Source: leetcode | Difficulty: MEDIUM
Tags: Matrices

Dynamic programming

Data structures

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 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


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]
		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:
		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:

	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)
		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
					dp[i + 1][j + 1][1] = dp[i + 1][j][1] + 1
		ans = 0
		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


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


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
		if self.accessGrid(grid, maxRowBound, maxColBound) == 1:
			k = maxColBound
			while k != j and self.accessGrid(grid, maxRowBound, k) == 1:
				k -= 1
			if k != j:
				return False
			s = maxRowBound
			while s != i and self.accessGrid(grid, s, maxColBound) == 1:
				s -= 1
			if s == i:
				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])
		i = 0
		j = 0
		largest_square = 0
		while i < self.rows:
			while j < self.cols:
				search_increment = 1
				if grid[i][j] == 1:
					if largest_square == 0:
						largest_square = 1
					if j != self.cols - 1:
						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
				remaining_search_space = (self.cols - j) ** 2
				if largest_square >= remaining_search_space:
					break
			i += 1
			j = 0
			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
				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)
				elif 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)
		maxGrid = 0
		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
				for span in range(minSpan, -1, -1):
					cSpanLeft = c - span + 1
					rSpanUp = r - span + 1
					if dp[r][cSpanLeft][0] >= span and dp[rSpanUp][c][1] >= span:
						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] & 255 if j else 0) + 1
				u = (grid[i - 1][j] >> 8 & 255 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] & 255 > 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:
		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, 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:
		(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
		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)
					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 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 largest1BorderedSquare(self, grid: List[List[int]]) -> int:
		if not grid:
			return 0
		m = len(grid)
		n = len(grid[0])
		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
		(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 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:
		(m, n) = (len(grid), len(grid[0]))
		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
		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 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:
		(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, grid: List[List[int]]) -> int:
		(m, n) = (len(grid), len(grid[0]))
		horizontal_len = [row[:] for row in grid]
		vertical_len = [row[:] for row in grid]
		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):
					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])
					if valid_width >= width:
						return width ** 2
		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:
		n = len(grid)
		m = len(grid[0])
		rows = [[0 for j in range(m + 1)] for i in range(1 + n)]
		cols = [[0 for j in range(m + 1)] for i in range(1 + n)]
		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):
			sum_row[i][0] = grid[i][0]
			for j in range(1, n):
				sum_row[i][j] = sum_row[i][j - 1] + grid[i][j]
		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]
		num_ele = 0
		for i in range(m):
			for j in range(n):
				l = min(i, j)
				for k in range(l + 1):
					slen = l - k
					length = slen + 1
					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))
		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
		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):
					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:
		if not grid:
			return 0
		m = len(grid)
		n = len(grid[0])
		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


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
					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:

	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