[C++] Nice, concise solution (runtime: 0 ms)
Others have come up with fundamentally the same solution, time complexity O(R * C * min(R, C)).\n\nBut I thought I\'d share my version anyway. It\'s concise, an
Others have come up with fundamentally the same solution, time complexity _O(R * C * min(R, C))_.\n\nBut I thought I\'d share my version anyway. It\'s concise, and it has some nice optimizations in the final code-block. For example, we never test a square unless it can beat our current best length.\n\n```C++\nint largest1BorderedSquare(vector<vector<int>>& grid) {\n  // grid size\n  const int R = grid.size();\n  const int C = grid[0].size();\n\n  // record the reach of 1\'s from every cell\n  auto right = grid;\n  auto down  = move(grid);\n  for (int r = 0; r < R; ++r)\n    for (int c = C-2; c >= 0; --c)\n      right[r][c] *= right[r][c+1] + 1;\n  for (int c = 0; c < C; ++c)\n    for (int r = R-2; r >= 0; --r)\n      down[r][c] *= down[r+1][c] + 1;\n\n  // find the largest 1-bordered square\n  int length = 0;\n  for (int r = 0; r < R - length; ++r)\n    for (int c = 0; c < C - length; ++c)\n      for (int dist = min(right[r][c], down[r][c]); dist > length; --dist)\n        if (dist <= min(right[r+dist-1][c], down[r][c+dist-1]))\n          length = dist;\n\n  return length * length;\n}\n```
['C']