# Largest 1-Bordered Square
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/largest-1-bordered-square)
Canonical: https://scaleengineer.com/dsa/problems/largest-1-bordered-square
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming)
**Data structures:** Array, Matrix
**Companies:** [Samsung](https://scaleengineer.com/companies/samsung), [DE Shaw](https://scaleengineer.com/companies/de-shaw), [ZS Associates](https://scaleengineer.com/companies/zs-associates)
---
## Problem
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`

# Approaches
## Brute Force Enumeration
This straightforward approach involves iterating through every possible top-left corner and every possible size for a square subgrid. For each potential square, it explicitly checks if all four borders consist of '1's.
**Time:** O(m * n * min(m, n) * min(m, n)). For an N x N grid, this is O(N^4). There are O(N^3) possible squares, and verifying each takes O(N) time. · **Space:** O(1), as no extra space proportional to the input size is used.
**Pros:** Simple to understand and implement.; Uses constant extra space (`O(1)`).
**Cons:** Extremely inefficient due to multiple nested loops and redundant checks.; The time complexity of `O(N^4)` makes it infeasible for the given constraints, likely leading to a 'Time Limit Exceeded' error.
### Explanation
The algorithm uses three nested loops. The outer two loops select a cell `(r, c)` as the potential top-left corner of a square. The third loop iterates through possible side lengths `len`, starting from 1. For each combination of `(r, c, len)`, a helper function is called to verify the border. This helper function iterates along the top, bottom, left, and right edges of the potential square. If it finds any '0', it invalidates the square. If the square is valid, we update our record of the maximum side length found so far. This process is repeated for all possible squares in the grid.

```java
class Solution {
    public int largest1BorderedSquare(int[][] grid) {
        int rows = grid.length;
        int cols = grid[0].length;
        int maxLen = 0;
        for (int r = 0; r < rows; r++) {
            for (int c = 0; c < cols; c++) {
                for (int len = 1; r + len <= rows && c + len <= cols; len++) {
                    if (isBordered(grid, r, c, len)) {
                        maxLen = Math.max(maxLen, len);
                    }
                }
            }
        }
        return maxLen * maxLen;
    }

    private boolean isBordered(int[][] grid, int r, int c, int len) {
        // Check top and bottom borders
        for (int j = c; j < c + len; j++) {
            if (grid[r][j] == 0 || grid[r + len - 1][j] == 0) {
                return false;
            }
        }
        // Check left and right borders
        for (int i = r; i < r + len; i++) {
            if (grid[i][c] == 0 || grid[i][c + len - 1] == 0) {
                return false;
            }
        }
        return true;
    }
}
```
### Algorithm
1. Initialize `maxLen = 0`.
2. Iterate through each cell `(r, c)` of the grid, treating it as a potential top-left corner of a square.
3. For each `(r, c)`, iterate through all possible side lengths `len` from `1` up to the maximum possible from that corner (`min(rows - r, cols - c)`).
4. For each potential square defined by `(r, c)` and `len`, check if its border is composed entirely of `1`s.
   - This involves checking four sides: the top row from `c` to `c + len - 1` at row `r`, the bottom row at `r + len - 1`, the left column from `r` to `r + len - 1` at column `c`, and the right column at `c + len - 1`.
5. If all four sides consist of `1`s, update `maxLen = max(maxLen, len)`.
6. After checking all possibilities, return `maxLen * maxLen`.

## Dynamic Programming with Pre-computation
This optimized approach uses dynamic programming to avoid redundant calculations. It pre-computes the lengths of consecutive '1's extending horizontally to the left and vertically upwards from each cell. This information allows for a much faster verification of whether a potential square has a 1-border.
**Time:** O(m * n * min(m, n)). The pre-computation is O(m*n). The main loop is O(m*n), and inside it, the while loop can run up to min(m,n) times. For an N x N grid, this is O(N^3). · **Space:** O(m * n) to store the two DP tables, `hor` and `ver`.
**Pros:** Significantly more efficient than the brute-force approach.; Fast enough to pass the given constraints.; The use of DP tables effectively caches intermediate results, avoiding re-computation.
**Cons:** Requires extra space proportional to the grid size for the DP tables.
### Explanation
The core idea is to build two DP tables, `hor` and `ver`. `hor[i][j]` stores the number of consecutive '1's to the left of `grid[i][j]` (inclusive), and `ver[i][j]` stores the number of consecutive '1's above `grid[i][j]` (inclusive). After populating these tables, we iterate through the grid, considering each cell `(i, j)` as the potential bottom-right corner of a square. The maximum possible side length `side` for a square ending at `(i, j)` is `min(hor[i][j], ver[i][j])`. We then check if a square of this `side` is valid by using our DP tables to instantly look up the lengths of the corresponding top and left borders. We start with the largest possible `side` for `(i, j)` and decrease it until we find a valid square or the size becomes too small. This avoids the costly re-scanning of the brute-force method.

```java
class Solution {
    public int largest1BorderedSquare(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        int[][] hor = new int[m][n];
        int[][] ver = new int[m][n];

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1) {
                    hor[i][j] = (j > 0) ? hor[i][j - 1] + 1 : 1;
                    ver[i][j] = (i > 0) ? ver[i - 1][j] + 1 : 1;
                }
            }
        }

        int maxLen = 0;
        for (int i = m - 1; i >= 0; i--) {
            for (int j = n - 1; j >= 0; j--) {
                int side = Math.min(hor[i][j], ver[i][j]);
                while (side > maxLen) {
                    // Check if the top and left borders are valid
                    if (ver[i][j - side + 1] >= side && hor[i - side + 1][j] >= side) {
                        maxLen = side;
                        break; // Found the largest square for this corner
                    }
                    side--;
                }
            }
        }
        return maxLen * maxLen;
    }
}
```
### Algorithm
1. Create two DP tables, `hor[m][n]` and `ver[m][n]`, to store lengths of consecutive `1`s.
2. Populate `hor` and `ver` in a single pass (`O(m*n)`):
   - For each cell `(i, j)`:
   - If `grid[i][j] == 1`:
     - `hor[i][j] = (j > 0) ? hor[i][j-1] + 1 : 1;`
     - `ver[i][j] = (i > 0) ? ver[i-1][j] + 1 : 1;`
3. Initialize `maxLen = 0`.
4. Iterate through the grid from bottom-right to top-left (`i` from `m-1` to `0`, `j` from `n-1` to `0`).
5. For each cell `(i, j)`, determine the maximum possible side length for a square ending at this corner: `side = min(hor[i][j], ver[i][j])`.
6. Check for a valid square by shrinking `side` downwards:
   - `while (side > maxLen)`:
     - A square of size `side` needs its top and left borders to be long enough.
     - Check if `ver[i][j - side + 1] >= side` (left border) and `hor[i - side + 1][j] >= side` (top border).
     - If both are true, a valid square is found. Update `maxLen = side` and break the inner `while` loop.
     - Otherwise, decrement `side` and check again.
7. Return `maxLen * maxLen`.

# Solutions
### Java

```java
class Solution {
public
  int largest1BorderedSquare(int[][] grid) {
    int m = grid.length, n = grid[0].length;
    int[][] down = new int[m][n];
    int[][] right = new int[m][n];
    for (int i = m - 1; i >= 0; --i) {
      for (int j = n - 1; j >= 0; --j) {
        if (grid[i][j] == 1) {
          down[i][j] = i + 1 < m ? down[i + 1][j] + 1 : 1;
          right[i][j] = j + 1 < n ? right[i][j + 1] + 1 : 1;
        }
      }
    }
    for (int k = Math.min(m, n); k > 0; --k) {
      for (int i = 0; i <= m - k; ++i) {
        for (int j = 0; j <= n - k; ++j) {
          if (down[i][j] >= k && right[i][j] >= k && right[i + k - 1][j] >= k &&
              down[i][j + k - 1] >= k) {
            return k * k;
          }
        }
      }
    }
    return 0;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int largest1BorderedSquare(vector<vector<int>> &grid) {
    int m = grid.size(), n = grid[0].size();
    int down[m][n];
    int right[m][n];
    memset(down, 0, sizeof down);
    memset(right, 0, sizeof right);
    for (int i = m - 1; i >= 0; --i) {
      for (int j = n - 1; j >= 0; --j) {
        if (grid[i][j] == 1) {
          down[i][j] = i + 1 < m ? down[i + 1][j] + 1 : 1;
          right[i][j] = j + 1 < n ? right[i][j + 1] + 1 : 1;
        }
      }
    }
    for (int k = min(m, n); k > 0; --k) {
      for (int i = 0; i <= m - k; ++i) {
        for (int j = 0; j <= n - k; ++j) {
          if (down[i][j] >= k && right[i][j] >= k && right[i + k - 1][j] >= k &&
              down[i][j + k - 1] >= k) {
            return k * k;
          }
        }
      }
    }
    return 0;
  }
};

```

### Python

```python
class Solution:
    def largest1BorderedSquare(self, grid: List[List[int]]) -> int: m, n = len(grid), len(grid[0]) down = [[0] * n for _ in range(m)] right = [[0] * n for _ in range(m)] for i in range(m - 1, - 1, - 1): for j in range(n - 1, - 1, - 1): if grid[i][j]: down[i][j] = down[i + 1][j] + 1 if i + 1 < m else 1 right[i][j] = right[i][j + 1] + 1 if j + 1 < n else 1 for k in range(min(m, n), 0, - 1): for i in range(m - k + 1): for j in range(n - k + 1): if (down[i][j] >= k and right[i][j] >= k and right[i + k - 1][j] >= k and down[i][j + k - 1] >= k): return k * k return 0

```