O(n^2) space and runtime. Sophisticated. With explanation. How to improve explanation/code?
Please comment for any suggestions how to explain better, code cleaner and any point, which should be clarified.\n\nI assume for simplicity that n is the maximu
Please **comment** for any suggestions how to *explain better*, *code cleaner* and any point, which should be clarified.\n\nI assume for simplicity that n is the maximum side length of the grid and show runtime O(n^2). The analysis can be adapted to non-rectangular grids to show that the runtime is, in fact, linear in n* m, the number of entries of the grid. This is asymtotically optimal. \n\nBefore we try ourselves finding full squares, we ask ourselves the following question:\nGiven a position (x,y) what is the longest possible sqare at this corner if we are allowed to set all values outside of row x and column y to 1. In other word, we are looking vor the maximum size of such a shape (where * denotes any value) where the upper right corner is (x,y).\n1 1 1 1 \n1 * * * \n1 * * *\n1 * * *\nThis value is UpperLeft[y][x];\nIn order to compute it efficiently (i.e. in time O(n^2)) we make yet another observation: If h is maximal such that \ngrid[y][x]=UpperLeft[y+1][x]=... UpperLeft[y+h-1][x]=1 and w is maximal such that grid[y][x]=UpperLeft[y][x+1]=... UpperLeft[y][x+w-1]=1 then UpperLeft[y][x]=min(w,h).\n\nAnaloguously we define LowerRight[y][x] to be the maximum size of a square whose lower right corner is (x,y) if we are allowed to set all values outside of column y and row x to 1. It corresponds to the following shape:\n, * * *  1 \n, * * *  1\n, * * *  1\n, 1 1 1 1\n(Commas are only added for formatting reasons.) It is computed analoguously to UpperLeft.\n\nNow we have the following observation: There exists a 1-Bordered Square with side length s and upper right corner (x,y) --- the lower left corner is thus (x+s-1,y+s-1) --- if and only if UpperLeft[y][x]>=s and LowerRight[y+s-1,y+s-1]>=s.\nWe now implement the following **subroutine** in linear time: Given a value best and a value d, we consider the diagonal defined by x-y=d; we then find out, whether there exists a 1-Bordered Square whose upper right and lower left corner lie in the diagonal and whose side-length is at least left. \n\nThe idea is the following. We start on the upper left of the diagonal x+d=y and proceed downwards (rightwards). The point (leftX,leftY) starts by (0,0) while (rightX,rightY)=(leftX+best,leftX+best). Whenever (leftX,leftY) could be a corner of a Square of sidelength at least best+1, i.e. if UpperLeft[leftY][leftX]>best, we add this corner to a stack. If (rightX,rightY) is a suitable lower right corner, i.e. rval=LowerRight[rightY][rightX]>best we check the values in the upper left corners if they form a Square. If the top element of the stack has distance *dist* more than rval from (rightX,right Y) there is no suitable square at that point. The situation might look like the following:\n1 1 1 1 1 1\n1   *  *  * * 0\n1   * * *   * 1\n1   * * *  *  1\n1   * * * *   1\n1 1 1 1 1 1 The two sides starting at the lower right corner do not reach the two sides starting at the upper left.\n\nOn the other hand, let lval be the value of UpperLeft of the top element of the stack. if(lval< dist). The top element is not a suitable left corner anymore. Furthermore, it will not be a suitable corner to any right corner we encounter later in the stack. We can pop/remove it. The situation could be the following:\n1  1 1 1 0 1\n1  *  *  * * 1\n1  * * *   * 1\n1  * * *  *  1\n1  * * * *   1\n1 1 1 1 1 1 The two sides at the upper left are not long enough.\nWe repeat the process till either the stack is empty or the right corner has rval smaller then the distance to the top element of the stack **or** till both the top element of the stack and the lower right corner have UpperLeft resp. LowerRight at least their distance *dist*. In this case they form a square of side length *dist*. Since we only put elements in the stack, which ahve distance at lest best+1 from the lower right corner, this square has side length at least *best*. One can also note that if such a square exists, the subroutine will find such a square (though not necessarily the best one). Finally, for the runtime, one should observe that the soubroutine whenever it checks a lower right corner either pops an element from the stack or finds out whether the right corner can be the right corner of a square of side length at least best+1. Since there are only n (number of element s on a diagonal) right corners and also at most n elements (corresponding to upper left corners) get added to the stack, this subroutine has runtime O(n).\n\nOur algorithm now does the following. Set best=0. For each diagonal check using our **subroutine** if it contains a square of size at least best+1. If so, set best to the size of the largest square found and repeat. Else, consider the next diagonal. \nIn each iteration we either increase best or consider a new diagonal. Since there are only 2n-1 diagonals and best cannot exceed n this means we use our subroutine at most 3n times. We get quadratic running time.\n\nPlease **comment** for any suggestions how to *explain better*, *code cleaner* and any point, which should be clarified.\n\nAs a new **challenge**, bring down the space requirements to O(n). You are not allowed to change the entries of *grid*, that is cheating. I am certain it is possible.\n\n\n```\nclass Solution {\npublic:\n    int largest1BorderedSquare(vector<vector<int>>& grid) {\n        \n        vector<vector<int>> upperLeft(grid.size(),vector<int>(grid[0].size()));\n        vector<vector<int>> lowerRight(grid.size(),vector<int>(grid[0].size()));\n        \n        for(int i=0;i<grid.size();++i){\n            computeHorizontalSums(upperLeft[i].rbegin(),upperLeft[i].rend(),grid[i].rbegin());\n            computeHorizontalSums(lowerRight[i].begin(),lowerRight[i].end(),grid[i].begin());\n        }\n        updateVerticalSums(upperLeft.rbegin(),upperLeft.rend(),grid.rbegin());\n        updateVerticalSums(lowerRight.begin(),lowerRight.end(),grid.begin());\n        \n        int best=0;\n                \n        for(int diagonal=1-grid.size(); diagonal<(int)grid[0].size(); ++diagonal){\n            bool couldImproveBest;\n            do{\n                couldImproveBest=false;\n                int rightX,leftX,rightY,leftY;\n                rightX=leftX=max(0,diagonal);\n                rightY=leftY=max(-diagonal,0);\n                int count=0;\n                \n\n                //(rightX,rightY) becomes the first point on the diagonal with distance best+1\n                while(rightY<grid.size() && rightX<grid[0].size() &&count<best){\n                    count++;\n                    rightX++;\n                    rightY++;\n                }\n                if(rightY<grid.size() && rightX<grid[0].size()){\n                    stack<pair<int,int>> possibleUpperLeftCorner;\n                    while(rightY<grid.size() && rightX<grid[0].size()){\n                        if(upperLeft[leftY][leftX]>best){\n                            possibleUpperLeftCorner.push(make_pair(leftX,leftY));\n                        }\n                        int rval=lowerRight[rightY][rightX];\n                        if(rval>best){\n                            int dist=INT_MAX;\n                            if(!possibleUpperLeftCorner.empty())\n                                dist=rightX-possibleUpperLeftCorner.top().first+1;\n                            while(rval>=dist){\n                                pair<int,int> current=possibleUpperLeftCorner.top();\n                                int lval=upperLeft[current.second][current.first];\n                                if(lval>=dist){\n                                    best=dist;\n                                    couldImproveBest=true;\n                                }\n                                \n                                possibleUpperLeftCorner.pop();\n                                if(possibleUpperLeftCorner.empty())\n                                    dist=INT_MAX;\n                                else\n                                    dist=rightX-possibleUpperLeftCorner.top().first+1;\n                            }\n                        }\n                        rightX++;\n                        rightY++;\n                        leftX++;\n                        leftY++;\n                    }\n                }\n            }while(couldImproveBest);\n        }\n        \n        return best*best;\n    }\nprivate:\n    template <class RandomAccessIterator> void computeHorizontalSums(RandomAccessIterator begin, RandomAccessIterator end, RandomAccessIterator gridposition){\n        if(*gridposition)\n            *begin=1;\n        else\n            *begin=0;\n        begin++;\n        while(begin!=end){\n            gridposition++;\n            if(*gridposition)\n                *begin=*(begin-1)+1;\n            else\n                *begin=0;\n            begin++;\n        }\n    }\n    template <class RandomAccessIterator> void updateVerticalSums(RandomAccessIterator begin, RandomAccessIterator end, RandomAccessIterator gridposition){\n        int n=begin->size();\n        \n        for(int i=0;i<n;++i){\n            RandomAccessIterator pos=gridposition;\n            int sum=0;\n            for(RandomAccessIterator it=begin;it!=end;++it){\n                if((*pos)[i])\n                    sum++;\n                else\n                    sum=0;\n                pos++;\n                (*it)[i]=min((*it)[i],sum);\n            }\n        }\n    }\n};\n```
[]