C++ || Pre-Count || Time 8ms >83% || Space 14MB >60%
Approach\nWe want to start form the largest square, check if it is 1-bordered, and if not move on to the next largest square. This is done with plain iteration.
# Approach\nWe want to start form the largest square, check if it is 1-bordered, and if not move on to the next largest square. This is done with plain iteration. To efficiently check if a square is 1-bordered, we can pre-count the number of consecutive 1\'s across the rows and the columns. Then we can immediately check if a square if 1-bordered by accessing the pre-counted values for the 4 corners.\n\n# Complexity\n- Time complexity:\nO(n*m^2) *, where n and m are the large and smaller dimensions of the grid respectively*\n\n- Space complexity:\nO(n*m) *, where n and m are the large and smaller dimensions of the grid respectively*\n\n# Code\n```\nclass Solution {\npublic:\n\tint largest1BorderedSquare(vector<vector<int>>& grid) {\n\t\tvector<vector<int>> cntrows(grid.size(), vector<int>(grid[0].size()));\n\t\tvector<vector<int>> cntcols(grid.size(), vector<int>(grid[0].size()));\n\n\t\t// pre-count consecutive 1\'s across rows\n\t\tfor (int j = 0; j < grid[0].size(); j++) {\n\t\t\tcntrows[0][j] = grid[0][j];\n\t\t}\n\t\tfor (int i = 1; i < grid.size(); i++) {\n\t\t\tfor (int j = 0; j < grid[0].size(); j++) {\n\t\t\t\tcntrows[i][j] = grid[i][j] * (cntrows[i - 1][j] + 1);\n\t\t\t}\n\t\t}\n\n\t\t// pre-count consecutive 1\'s across cols\n\t\tfor (int j = 0; j < grid.size(); j++) {\n\t\t\tcntcols[j][0] = grid[j][0];\n\t\t}\n\t\tfor (int i = 1; i < grid[0].size(); i++) {\n\t\t\tfor (int j = 0; j < grid.size(); j++) {\n\t\t\t\tcntcols[j][i] = grid[j][i] * (cntcols[j][i - 1] + 1);\n\t\t\t}\n\t\t}\n\n\t\t// check progressively smaller square\n\t\tfor (int dimm = min(grid.size(), grid[0].size()); dimm >= 0; dimm--) {\n\t\t\tfor (int i = 0; i < grid.size() - dimm; i++) {\n\t\t\t\tfor (int j = 0; j < grid[0].size() - dimm; j++) {\n\t\t\t\t\tif (cntrows[i + dimm][j] > dimm &&\n\t\t\t\t\t\tcntrows[i + dimm][j + dimm] > dimm &&\n\t\t\t\t\t\tcntcols[i][j + dimm] > dimm &&\n\t\t\t\t\t\tcntcols[i + dimm][j + dimm] > dimm) {\n\t\t\t\t\t\treturn (dimm + 1) * (dimm + 1);\n\t\t\t\t\t}\n\t\t\t\t}\n\t\t\t}\n\t\t}\n\n\t\t// no 1-bordered square found\n\t\treturn 0;\n\t}\n};\n```
['C++']