> For the complete documentation index, see [llms.txt](https://mayanktyagi3111.gitbook.io/interview-prep/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://mayanktyagi3111.gitbook.io/interview-prep/dynamic-programming/untitled-9.md).

# Largest 1-Bordered Square

Given a 2D `grid` of `0`s and `1`s, return the number of elements in the largest **square** subgrid that has all `1`s on its **border**, or `0` if such a subgrid doesn't exist in the `grid`.

**Example 1:**

```
Input: grid = [[1,1,1],[1,0,1],[1,1,1]]
Output: 9
```

**Example 2:**

```
Input: grid = [[1,1,0,0]]
Output: 1
```

**Constraints:**

* `1 <= grid.length <= 100`
* `1 <= grid[0].length <= 100`
* `grid[i][j]` is `0` or `1`

***Explaination:***

Create auxillary horizontal and vertical arrays first\
For example :<br>

![image](https://assets.leetcode.com/users/goelrishabh5/image_1564287873.png)

Then starting from bottom right,for every i,j ; we find small=min (ver\[i]\[j], hor\[i]\[j]) (marked in orange) , then look at all distances in \[1,small] vertically in hor array and horizontally in ver array. If values(shown in blue) are greater than small and if small is greater than curr result, then we update result<br>

![image](https://assets.leetcode.com/users/goelrishabh5/image_1564288202.png)

```java
class Solution {
    public int largest1BorderedSquare(int[][] grid) {
        int m = grid.length, n = grid[0].length;
        int[][] ver = new int[m][n];
        int[][] hor = new int[m][n];
        for (int j = 0; j < n; j++) {
            for (int i = 0; i < m; i++) {
                if (i == 0)
                    ver[i][j] = grid[i][j];
                else
                    ver[i][j] = grid[i][j] == 1 ? (ver[i - 1][j] + grid[i][j]) : 0;
                if (j == 0)
                    hor[i][j] = grid[i][j];
                else
                    hor[i][j] = grid[i][j] == 1 ? (hor[i][j - 1] + grid[i][j]) : 0;
            }
        }
        int max = 0;
        for (int i = m - 1; i >= 0; i--) {
            for (int j = n - 1; j >= 0; j--) {
                int small = Math.min(hor[i][j], ver[i][j]); // choose smallest of horizontal and vertical value
                while (small > max) {
                    if (ver[i][j - small + 1] >= small && hor[i - small + 1][j] >= small)
                        // check if square exists with 'small' length
                        max = small;
                    small--;
                }
            }
        }
        return max * max;
    }
}
```