Java Solution With Explanation
Idea\nleft[i][j] indicates how far left can we go from [i][j] cell.\nup[i][j] indicates how far up can we go from [i][j] cell.\n\nNow, at every [i][j], we will 
**Idea**\n`left[i][j]` indicates how far left can we go from `[i][j]` cell.\n`up[i][j]` indicates how far up can we go from `[i][j]` cell.\n\nNow, at every `[i][j]`, we will start with verifying max square has `1-border`. The max square has length `d` which is the min of `left[i][j]` and `up[i][j]` (i.e. since it is a square, how far up and left we can go will be determined by the min of those two, right?).\nNow, we may not have max square with `d`, how do we check? we move up `d` steps and check the `left` there to see if that cell has the value at least `d`, why? then we can go left from there by `d` steps to form the square. Similar check - we move left `d` steps and check the `up` there.\nand then we will keep trying smaller square at `d-1`, if the above checks fail.\n\n```\npublic int largest1BorderedSquare(int[][] g) {\n        int m = g.length, n = g[0].length;\n        int[][] left = new int[m][n], up = new int[m][n];\n        for(int i=0; i < m; i++){\n            left[i][0] = g[i][0];\n            for(int j=1; j < n; j++)\n                if(g[i][j] == 1)\n                    left[i][j] = 1+left[i][j-1];\n        }\n        for(int j=0; j < n; j++){\n            up[0][j] = g[0][j];\n            for(int i=1; i < m; i++)\n                if(g[i][j] == 1)\n                    up[i][j] = 1+up[i-1][j];\n        }\n        int max = 0;\n        for(int i=0; i < m; i++){\n            for(int j=0; j < n; j++){\n                int d = Math.min(left[i][j], up[i][j]);\n                while(d > 1){\n                     if(left[i-(d-1)][j] >= d && up[i][j-(d-1)] >= d)\n                         break;\n                    --d;\n                }\n                max = Math.max(max, d*d);\n            }\n        }\n        return max;\n    }\n```
[]