Given a 2D grid of 0s and 1s, return the number of elements in&nbsp;the largest square&nbsp;subgrid that has all 1s on its border, or 0 if such a subgrid&nbsp;doesn't exist in the grid.

&nbsp;
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


&nbsp;
Constraints:


	1 &lt;= grid.length &lt;= 100
	1 &lt;= grid[0].length &lt;= 100
	grid[i][j] is 0 or 1

class Solution:
    def largest1BorderedSquare(self, grid: List[List[int]]) -> int:
        m = len(grid)
        n = len(grid[0])
        dp = [[[grid[i][j]] * 4 for j in range(n)] for i in range(m)]
        for i in range(m):
            for j in range(n):
                if i > 0:
                    if grid[i][j] == 1:
                        dp[i][j][1] = dp[i - 1][j][1] + 1
                if j > 0:
                    if grid[i][j] == 1:
                        dp[i][j][0] = dp[i][j - 1][0] + 1
        for i in range(m - 1, -1, -1):
            for j in range(n - 1, -1, -1):
                if i < m - 1:
                    if grid[i][j] == 1:
                        dp[i][j][2] = dp[i + 1][j][2] + 1
                if j < n - 1:
                    if grid[i][j] == 1:
                        dp[i][j][3] = dp[i][j + 1][3] + 1
        mside = min(m, n)
        for l in range(mside - 1, -1, -1):
            for i in range(m - l):
                for j in range(n - l):
                    if min(dp[i][j][2], dp[i][j][3], dp[i + l][j + l][0], dp[i + l][j + l][1]) >= l + 1:
                        return (l + 1) * (l + 1)
        return 0
class Solution {
    public int largest1BorderedSquare(int[][] grid) {
        int m=grid.length;
        int n=grid[0].length;
		// rows[r][c] is the length of the line ended at [r,c] on row r
        int[][] rows=new int[m][n];        
		// the length of the line ended at [r,c] on colume c
        int[][] cols=new int[m][n];
        int res=0;
        for(int r=0;r<m;r++){
            for(int c=0;c<n;c++){
                if(grid[r][c]==0){
                    rows[r][c]=0;
                    cols[r][c]=0;
                }else{
                    rows[r][c]=c==0?1:rows[r][c-1]+1;
                    cols[r][c]=r==0?1:cols[r-1][c]+1;
                    if(res>=rows[r][c]||res>=cols[r][c]){
                        continue;
                    }
                    res=Math.max(res,getD(rows,cols,r,c));
                }
            }
        }
        return res*res;
    }
    
	// get the dimension of the largest square which bottom-right point is [row,col]
    private int getD(int[][] rows,int[][] cols,int row,int col){
        int len=Math.min(rows[row][col],cols[row][col]);
        for(int i=len-1;i>=0;i--){
            if(rows[row-i][col]>i && cols[row][col-i]>i){
                return i+1;
            }
        }
        return 1;
    }
}
class Solution {
public:
    int largest1BorderedSquare(vector<vector<int>>& g) {
        int n=g.size();
        int m=g[0].size();
        int ver[n][m]; // to store lenght of continuous 1's vertically
        int hor[n][m]; // to store lenght of continuous 1's horizontally
		
		// fill vertical table
        for(int i=n-1;i>=0;i--){
            for(int j=0;j<m;j++){
                if(g[i][j]==1){
                    if(i==n-1) ver[i][j]=1;
                    else ver[i][j]=ver[i+1][j]+1;
                }
                else ver[i][j]=0;
            }
        }
        
		// fill horizontal table
        for(int i=n-1;i>=0;i--){
            for(int j=m-1;j>=0;j--){
                if(g[i][j]==1){
                    if(j==m-1) hor[i][j]=1;
                    else hor[i][j]=hor[i][j+1]+1;
                }
                else hor[i][j]=0;
            }
        }
        
		// Iterate through the all i and j and find best solution
        int ans=0;
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                if(!g[i][j]) continue;
                int temp=1;
                int k=min(hor[i][j],ver[i][j]);
                for(int p=1;p<k;p++){
                    int mn = min(hor[i+p][j],ver[i][j+p]);
                    if(mn>=p+1) temp=p+1;
                }
                ans=max(ans,temp);
            }
        }
        ans*=ans;
        return ans;
        
    }
};
var largest1BorderedSquare = function(grid) {
  let m = grid.length, n = grid[0].length;
  let top = Array(m).fill(0).map(() => Array(n).fill(0));
  let left = Array(m).fill(0).map(() => Array(n).fill(0));
  for (let i = 0; i < m; i++) {
    for (let j = 0; j < n; j++) {
      if (grid[i][j] === 1) {
        left[i][j] = j > 0 ? left[i][j - 1] + 1 : 1;
        top[i][j] = i > 0 ? top[i - 1][j] + 1 : 1;
      }
    }
  }

  let ans = 0;
  for (let i = 0; i < m; i++) {
    for (let j = 0; j < n; j++) {
      let size = Math.min(top[i][j], left[i][j]);
      for (let k = size; k > 0; k--) {
        let bottomLeftTop = top[i][j - k + 1];
        let topRightLeft = left[i - k + 1][j];
        if (bottomLeftTop >= k && topRightLeft >= k) {
          ans = Math.max(ans, k * k);
          break;
        }
      }
    }
  }
  return ans;
};
Largest 1-Bordered Square