Explained
IntuitionTo avoid repeated work, process the grid first;ApproachStore in all potential upper left corners the largest possible side length of the square, based
# Intuition
To avoid repeated work, process the grid first;

# Approach
Store in all potential upper left corners the largest possible side length of the square, based on the number of consecutive 1's horizontally and vertically. 
Also store in all potential bottom right corners likewise.
Then find the largest pair of upper-left and bottom-right corner.

# Complexity
- Time complexity:
$$O(n^2)$$


# Code
```cpp []
class Solution {
public:
    int largest1BorderedSquare(vector<vector<int>>& grid) {
        int m = grid.size();
        int n = grid[0].size();

        // Check if there is a 1, if not, return 0;
        bool hasOne = false;
        for (int i=0;i<m;i++) {
            for (int j=0;j<n;j++) {
                if (grid[i][j]==1) {hasOne = true; break;}
            }
            if (hasOne) break;
        }
        if (!hasOne) return 0;

        // create 4 matrices, each entry stores:
        // in A: the longest horizontal side length with entry position being the right end;
        // in B: the longest vertical side length with entry position being the bottom end;
        // in C: the longest horizontal side length with entry position being the left end;
        // in D: the longest vertical side length with entry position being the top end;
        vector<vector<int>> A = grid, B = grid, C = grid, D = grid;
        for (int i=0;i<m;i++) {
            for (int j=0;j<n;j++) {
                if (j>0&&A[i][j-1]!=0&&A[i][j]!=0) A[i][j]+=A[i][j-1];
                if (j>0&&C[i][n-j]!=0&&C[i][n-j-1]!=0) C[i][n-j-1]+=C[i][n-j];
                if (i>0&&B[i-1][j]!=0&&B[i][j]!=0) B[i][j]+=B[i-1][j];
                if (i>0&&D[m-i][j]!=0&&D[m-i-1][j]!=0) D[m-i-1][j]+=D[m-i][j];
            }
        }

        // Update A and C such that each entry stores the longest segment length that can be both vertical and horizontal, with the position of each entry being:
        // in A: the bottom right corner;
        // in C: the upper left corner;
        for (int i=0;i<m;i++) {
            for (int j=0;j<n;j++) {
                A[i][j] = min(A[i][j],B[i][j]);
                C[i][j] = min(C[i][j],D[i][j]);
            }
        }

        int res = 1;
        // loop through C, the upper left corner, and check if the bottom right corner is in A;
        for (int i=0;i<m;i++) {
            for (int j=0;j<n;j++) {
                for (int a=C[i][j]; a>res; a--) {
                    if (A[i+a-1][j+a-1]>=a) {
                        res = a;
                        break;
                    }
                }
            }
        }

        return res*res;
    }
};
```
['C++']