C++ | DP
Intuition & Approach\n Describe your first thoughts on how to solve this problem. \nPrefix sum is hinted by forming a square, at a point we can get to know if i
# Intuition & Approach\n<!-- Describe your first thoughts on how to solve this problem. -->\nPrefix sum is hinted by forming a square, at a point we can get to know if its a square if number of 1\'s form a square.\nSo, compute prefixSum for both rows and cols, and process the complete array again.\n\n# Complexity\n- Time complexity: O(rows*cols*min(rows, cols))\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: O(rows*cols)\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution {\npublic:\n    int largest1BorderedSquare(vector<vector<int>>& grid) {\n        int rows = grid.size(), cols = grid[0].size();\n        int res = 0;\n        bool ones = false;\n        int rowSum[rows][cols], colSum[rows][cols];\n        // vector<vector<int>> rowSum(rows, vector<int>(cols, 0)), colSum(rows, vector<int>(cols, 0));\n        \n        // calculate the prefix sum\n        for(int i = 0; i < rows; i++)\n        {\n            for(int j = 0; j < cols; j++)\n            {\n                if(grid[i][j] == 0)\n                    rowSum[i][j] = colSum[i][j] = 0;\n                else\n                {\n                    ones = true;\n                    rowSum[i][j] = j > 0 ? rowSum[i][j-1] + 1 : 1;\n                    colSum[i][j] = i > 0 ? colSum[i-1][j] + 1 : 1;\n                }\n            }\n        }\n\n        // now compute the actual result by taking each point and then \\\n            calculate the maximum square area possible.\n        for(int i = 1; i < rows; i++)\n        {\n            for(int j = 1; j < cols; j++)\n            {\n                // i, j\n                // traverse the complete length.\n\n                int maxLen = min(i, j); // how many steps we can move up to check.\n                int bottomRow = rowSum[i][j], bottomCol = colSum[i][j];\n                for(int k = maxLen; k >= 1; k--)\n                {\n                    int newRow = rowSum[i-k][j], newCol = colSum[i][j-k];\n                    int len = k+1;\n                    int minNum = min(bottomRow, min(bottomCol, min(newRow, newCol)));\n\n                    if(minNum >= len)\n                    {\n                        res = max(res, len*len);\n                        break;\n                    }\n                }\n            }\n        }\n        return res == 0 ? ones : res;\n    }\n};\n```
['C++']