Java, DP with explanation. Beats 100%
Intuition\nA square border comprises of 4 parts, 2 vertical lines and 2 horizontal lines. The length of side of square formed from these 4 lines of varying leng
# Intuition\nA square border comprises of 4 parts, 2 vertical lines and 2 horizontal lines. The length of side of square formed from these 4 lines of varying length will be the minimum of the four lines.\n\n# Approach\nIf we could find the length of these four lines mentioned above and then find the minimum of the four and then square it, we would get the required answer.\n\nTo do so, I kept a count of number of consecutive ones occuring vertically and the number of consecutive ones appearing horizontally with the help of two 2D arrays, namely `horizontal_count` and `vertica_count`.\n\nAfter which it is a simple nested for-loop to check for squares by checking if length of all the four sides is greater than our current answer\n\n\n\n# Code\n```\nclass Solution {\n    public int largest1BorderedSquare(int[][] grid) {\n        int horizontal_count[][]=new int [grid.length][grid[0].length];\n        int vertical_count[][]=new int [grid.length][grid[0].length];\n        int ans=1,flag=0;\n        for(int i=0;i<grid.length;i++)\n        {\n            int c=0;\n            for(int j=grid[0].length-1;j>=0;j--)\n            {\n                if(grid[i][j]==1)\n                {\n                    flag=1;\n                    c++;\n                    horizontal_count[i][j]=c;\n                }\n                else\n                c=0;\n            }\n        }\n        if(flag==0)\n        return 0;\n        for(int i=0;i<grid[0].length;i++)\n        {\n            int c=0;\n            for(int j=grid.length-1;j>=0;j--)\n            {\n                if(grid[j][i]==1)\n                {\n                    c++;\n                    vertical_count[j][i]=c;\n                }\n                else\n                c=0;\n            }\n        }\n        for(int i=0;i<grid.length;i++)\n        {\n            for(int j=0;j<grid[0].length;j++)\n            {\n                if(vertical_count[i][j]>ans)\n                {\n                    int temp=vertical_count[i][j]>=horizontal_count[i][j]?horizontal_count[i][j]:vertical_count[i][j];\n                    if(j-1+temp>=grid[0].length)\n                    temp=grid[0].length-j-1;\n                    if(i-1+temp>=grid.length)\n                    temp=grid.length-i-1;\n                    if(temp<ans)\n                    continue;\n                    while(temp>ans)\n                    {\n                        if(temp<=vertical_count[i][j-1+temp]&&temp<=horizontal_count[i-1+temp][j])\n                        {\n                            ans=temp;\n                            break;\n                        }\n                        else\n                        temp--;\n                    }\n                }\n            }\n        }\n        return ans*ans;\n    }\n}\n```
['Dynamic Programming', 'Java']