O(N^2logN) solution
The basic idea is to preprocess the length of two types of gadget at each position:\n\n[X is current position]\nType A:\ntext\n    1\n    1\n1 1 X\n\nwhich has 
The basic idea is to preprocess the length of two types of gadget at each position:\n\n[X is current position]\nType A:\n```text\n    1\n    1\n1 1 X\n```\nwhich has length min(left[i, j], top[i, j]). Here it\'s 3.\n\nType B:\n```\nX 1 1\n1\n1\n```\n\nwhich has length min(right[i, j], bottom[i, j]), which is 3 in this example.\n\nThen, for each top-left -> bottom right diagnal line, we try to match these two types of gadget. Assume we are currently at row `i` with gadget A of length `dself`, we want to find matching gadget Bs at row `i\' <= i` with gadget length `d_i\'` (i.e., min(r[i\', j\'], b[i\', j\'])) and choose the one that forms a max border square, i.e.,\n1) `i - dself + 1` <= `i\'` <= `i`\n2) `i\' + d_i\'` >= `i`\n\nAnd the one that forms the largest square is the minimal `i\'` that satisfies the above conditions.\n\nWe can maintain two balance trees for each of the condition. For each `i`, we first add `i + d_i` to `max_reach` tree and `i` to `s` tree. Then, note that `i` is increasing, so we can pop all `i\'` along with their entries in `s` that have `i\' + d_i\' < i`. After this operation, all entries in `s` and `max_reach` satisfies condition 2). Therefore, we can use a binary search in `s` tree to find the minimum `i\'` s.t., `i - dself + 1 <= i\'`.\n\n```cpp\nclass Solution {\npublic:\n    int largest1BorderedSquare(vector<vector<int>>& grid) {\n        const int m = grid.size(), n = grid[0].size();\n        // consecutive 1s to left/right/top/bottom\n        vector<int> l(m * n), r(m * n), t(m * n), b (m * n);\n        auto idx = [m, n](int i, int j) {\n            return i * n + j;\n        };\n        for (int i=0; i<m; ++i) {\n            l[idx(i, 0)] = grid[i][0];\n            for (int j= 1; j<n; ++j)\n                l[idx(i, j)] = grid[i][j] ? l[idx(i, j-1)] + 1 : 0;\n            r[idx(i, n-1)] = grid[i][n-1];\n            for (int j =n-2; j>=0; --j)\n                r[idx(i, j)] = grid[i][j] ? r[idx(i, j+1)] + 1 : 0;\n        }\n        for (int j=0; j<n; ++j) {\n            t[idx(0, j)] = grid[0][j];\n            for (int i=1; i<m; ++i)\n                t[idx(i, j)] = grid[i][j] ? t[idx(i-1, j)] + 1 : 0;\n            b[idx(m-1, j)] = grid[m-1][j];\n            for (int i=m-2; i>=0; --i)\n                b[idx(i, j)] = grid[i][j] ? b[idx(i+1, j)] + 1 : 0;\n        }\n        int ans = 0;\n        // for each topleft -> bottomright diagnal line with i - j = d\n        for (int d = -max(m, n); d <= max(m, n); ++d)\n        {\n            set<pair<int, int>> max_reach; // <i\' + min(r, b), i\'>\n            set<int> s; // all i\' in max_reach\n            for (int i = 0; i < m; ++i)\n            {\n                int j = i - d;\n                if (j >= n) break;\n                if (j < 0) continue;\n                int dself = min(t[idx(i, j)], l[idx(i, j)]);\n                // find minimum i\' from i - dself + 1, s.t. \n                // i\' + min(r[i\', j\'], b[i\', j\']) >= i\n                s.insert(i);\n                max_reach.insert(make_pair(i + min(r[idx(i, j)], b[idx(i, j)]), i));\n                while (!max_reach.empty() && max_reach.begin()->first < i)\n                {\n                    s.erase(max_reach.begin()->second);\n                    max_reach.erase(max_reach.begin());\n                }\n                auto it = s.lower_bound(i - dself + 1);\n                if (it != s.end())\n                    ans = max(ans, (i - *it + 1) * (i - *it + 1));\n            }\n        }\n        return ans;\n    }\n};\n```
['Binary Search Tree']