Simple Java Sol. | Beats 98% | Explanation
Intuition\n Describe your first thoughts on how to solve this problem. \n\n# Approach\n Simple brute force\n\n# Complexity\n- Time complexity:\n O(n^3)\n\n- Spa
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach\n Simple brute force\n\n# Complexity\n- Time complexity:\n O(n^3)\n\n- Space complexity:\n O(n^2)\n\n# Code\n```\nclass Solution {\n\n    public int largest1BorderedSquare(int[][] grid) {\n       int m = grid.length, n = grid[0].length;\n       int[][] hor = new int[m][n];\n       int[][] ver = new int[m][n];\n       \n       for(int i=0; i<grid.length; i++){ // count no. of 1\'s from right to  i,j (<----- this dir. in grid)\n        int cnt = 0;\n        for(int j =n-1; j >= 0; j--){\n            if(grid[i][j] == 1)\n             cnt++;\n            else cnt = 0;\n            hor[i][j] = cnt;\n        }\n       }\n   \n\n       for(int i=0; i<grid[0].length; i++){ // count no. of 1\'s from bottom to j,i\n        // ^\n        // |\n        // | this dir. in grid\n         int cnt = 0;\n        for(int j =m-1; j >= 0; j--){\n            if(grid[j][i] == 1)\n             cnt++;\n            else cnt = 0;\n            ver[j][i] = cnt;\n        }\n       }\n       \n        int max = 0;\n        for(int i =0; i<m; i++){\n            for(int j =0; j<n; j++){\n                int size = largestSquare(grid,i,j,hor,ver); // start from every possible idx\n                max= Math.max(max, size);\n            }\n        }\n        return max;\n    }\n\n    private int largestSquare(int[][] grid, int x, int y, int[][] hor, int[][] ver) {\n        if (x<0 || y<0 || x >= grid.length || y >= grid[0].length || grid[x][y] == 0) return 0;\n\n            int len = Math.min(hor[x][y],ver[x][y]) -1;// min dist b/w horiz & vert. line containing ones \n\n            for(int i =len; i>=0; i--){ // shrink if unable to make\n                if(i+x < grid.length && i+y <grid[0].length && ver[x][y+i]> i && hor[i+x][y] > i)\n                    return (i+1)*(i+1);\n            }\n\n            return 0;     \n    }\n}\n\n```
['Array', 'Dynamic Programming', 'Recursion', 'Matrix', 'Java']