Java code (Recursion/Backtracking)
Intuition

What we want: We need to find the biggest square in the grid where every cell along its border is a 1.


Key idea: Even if a smaller square doesn’t w
# Intuition
- **What we want**: We need to find the biggest square in the grid where every cell along its border is a 1.
 
- **Key idea**: Even if a smaller square doesn’t work because one of its border cells is 0, a bigger square might work because that 0 could end up inside the square (and we only care about the border).

# Approach
1. **Start at Every 1:**
Look at every cell in the grid. If it’s a 1, consider it as the top-left corner of a square.

2. **Try Different Sizes:**
From that starting cell, try making squares of different sizes (like 1x1, 2x2, 3x3, etc.) as long as the square fits in the grid.

3. **Check the Border:**
For each square, check if all the cells along its edges (top, bottom, left, right) are 1.

4. **Keep the Largest:**
If the square’s border is all 1s, update your record of the largest square you’ve found.

5. **Final Answer:**
After checking all possible squares, return the area (side length squared) of the largest valid square.

# Complexity
- Time complexity:
For every cell, we try many square sizes and check each square’s border. This makes the algorithm slower on large grids. In the worst-case, it can be thought of as checking about m × n × (size^2) cells, where m and n are the grid’s dimensions.

- Space complexity:
The primary extra space used is due to recursion. The maximum depth of recursion is K (the largest square side length). Hence, the space complexity is O(min(m, n)) (excluding the input grid).

# Code
```java []
class Solution {
    int rows, cols, maxSquare;
    int[][] grid;
    
    public int largest1BorderedSquare(int[][] g) {
        if (g == null || g.length == 0 || g[0].length == 0) return 0;
        grid = g;
        rows = grid.length;
        cols = grid[0].length;
        maxSquare = 0;
        
        // Try every cell as the top-left corner.
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (grid[i][j] == 1) {  // Only consider if the top-left is 1.
                    backtrack(i, j, 1);
                }
            }
        }
        return maxSquare * maxSquare;
    }
    
    // Recursively check all possible square sizes from (i, j)
    private void backtrack(int i, int j, int size) {
        // If the square goes out of bounds, stop recursion.
        if (i + size > rows || j + size > cols) return;
        
        // Check if the current square's border is all 1s.
        if (isValidBorder(i, j, size)) {
            if (size > maxSquare) {
                maxSquare = size;
            }
        }
        // Regardless of current validity, try a larger square.
        backtrack(i, j, size + 1);
    }
    
    // Check if the square with top-left at (i, j) and side length 'size'
    // has all 1s on its border.
    private boolean isValidBorder(int i, int j, int size) {
        // Check top and bottom rows.
        for (int col = j; col < j + size; col++) {
            if (grid[i][col] == 0) return false;               // Top border
            if (grid[i + size - 1][col] == 0) return false;      // Bottom border
        }
        // Check left and right columns (excluding corners already checked).
        for (int row = i + 1; row < i + size - 1; row++) {
            if (grid[row][j] == 0) return false;               // Left border
            if (grid[row][j + size - 1] == 0) return false;      // Right border
        }
        return true;
    }
}

```
['Backtracking', 'Recursion', 'Java']