Code Implementation

class Solution:
    def largest1BorderedSquare(self, grid):
        m, n = len(grid), len(grid[0])
        hor = [[0]*(n+1) for _ in range(m+1)]
        ver = [[0]*(n+1) for _ in range(m+1)]
        
        for i in range(m):
            for j in range(n):
                if grid[i][j]:
                    hor[i+1][j+1] = hor[i+1][j] + 1
                    ver[i+1][j+1] = ver[i][j+1] + 1

        max_side = 0
        for i in range(m):
            for j in range(n):
                small = min(hor[i+1][j+1], ver[i+1][j+1])
                while small > 0:
                    if hor[i+2-small][j+1] >= small and ver[i+1][j+2-small] >= small:
                        max_side = max(max_side, small)
                        break
                    small -= 1
        return max_side * max_side
      

class Solution {
public:
    int largest1BorderedSquare(vector<vector<int>>& grid) {
        int m = grid.size(), n = grid[0].size();
        vector<vector<int>> hor(m+1, vector<int>(n+1, 0)), ver(m+1, vector<int>(n+1, 0));
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (grid[i][j]) {
                    hor[i+1][j+1] = hor[i+1][j] + 1;
                    ver[i+1][j+1] = ver[i][j+1] + 1;
                }
            }
        }
        int max_side = 0;
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                int small = min(hor[i+1][j+1], ver[i+1][j+1]);
                while (small > 0) {
                    if (hor[i+2-small][j+1] >= small && ver[i+1][j+2-small] >= small) {
                        max_side = max(max_side, small);
                        break;
                    }
                    --small;
                }
            }
        }
        return max_side * max_side;
    }
};
      

class Solution {
    public int largest1BorderedSquare(int[][] grid) {
        int m = grid.length, n = grid[0].length;
        int[][] hor = new int[m+1][n+1];
        int[][] ver = new int[m+1][n+1];
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (grid[i][j] == 1) {
                    hor[i+1][j+1] = hor[i+1][j] + 1;
                    ver[i+1][j+1] = ver[i][j+1] + 1;
                }
            }
        }
        int maxSide = 0;
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                int small = Math.min(hor[i+1][j+1], ver[i+1][j+1]);
                while (small > 0) {
                    if (hor[i+2-small][j+1] >= small && ver[i+1][j+2-small] >= small) {
                        maxSide = Math.max(maxSide, small);
                        break;
                    }
                    small--;
                }
            }
        }
        return maxSide * maxSide;
    }
}
      

var largest1BorderedSquare = function(grid) {
    let m = grid.length, n = grid[0].length;
    let hor = Array.from({length: m+1}, () => Array(n+1).fill(0));
    let ver = Array.from({length: m+1}, () => Array(n+1).fill(0));
    for (let i = 0; i < m; ++i) {
        for (let j = 0; j < n; ++j) {
            if (grid[i][j]) {
                hor[i+1][j+1] = hor[i+1][j] + 1;
                ver[i+1][j+1] = ver[i][j+1] + 1;
            }
        }
    }
    let maxSide = 0;
    for (let i = 0; i < m; ++i) {
        for (let j = 0; j < n; ++j) {
            let small = Math.min(hor[i+1][j+1], ver[i+1][j+1]);
            while (small > 0) {
                if (hor[i+2-small][j+1] >= small && ver[i+1][j+2-small] >= small) {
                    maxSide = Math.max(maxSide, small);
                    break;
                }
                small--;
            }
        }
    }
    return maxSide * maxSide;
};
      

Problem Description

Given a 2D grid of integers, where each cell contains either a 0 or 1, your goal is to find the area of the largest square whose borders are all 1s. The square must be aligned with the grid (not rotated), and only the border cells of the square need to be 1s—the interior may contain 0s or 1s. You should return the area (side length squared) of the largest such square. If no such square exists, return 0.

• You can only use each cell as part of one square border at a time.
• There may be multiple squares, but you must find the one with the largest area.
• Input is a rectangular matrix: grid with m rows and n columns.

Thought Process

At first glance, you might think about checking every possible square in the grid to see if its border is all 1s. This brute-force approach would involve iterating over all possible top-left and bottom-right corners, and then checking each side of the square, which can be very slow for large grids.

However, this approach is inefficient because you would end up checking the same rows and columns repeatedly. To optimize, you can precompute information about how many consecutive 1s appear horizontally and vertically up to each cell. This way, you can quickly verify if a square's border is valid by just looking up values, instead of iterating through each border cell every time.

The key insight is to use dynamic programming to store these counts, reducing repeated work and making checks for valid borders fast.

Solution Approach

• Step 1: Precompute Consecutive 1s
  • Create two matrices: one for counting consecutive 1s horizontally for each cell, and one for vertically.
  • For each cell (i, j), if grid[i][j] is 1, update:
    • Horizontal count: number of consecutive 1s to the left (including itself).
    • Vertical count: number of consecutive 1s above (including itself).
• Step 2: Check for Largest Square
  • Iterate through each cell, treating it as the bottom-right corner of a possible square.
  • For each cell, compute the maximum possible square side length (based on horizontal and vertical counts at that cell).
  • For each possible side length (starting from the largest), check if the corresponding top border and left border also have enough consecutive 1s using the precomputed matrices.
  • If a valid square is found, update the maximum area and break (since we want the largest).
• Step 3: Return Result
  • After checking all cells, return the area of the largest square found (side length squared).

This approach leverages dynamic programming for fast lookups and avoids redundant work, making it much more efficient than brute-force.

Example Walkthrough

Consider the following grid as input:

    grid = [
      [1, 1, 1],
      [1, 0, 1],
      [1, 1, 1]
    ]
  

Let's walk through the steps:

1. Precompute horizontal and vertical counts:
   • For cell (2,2) (bottom-right corner), the horizontal and vertical counts are both 3, because there are three consecutive 1s to the left and above.
2. Check possible squares:
   • At cell (2,2), the largest possible square is size 3. Check if the top border and left border also have at least 3 consecutive 1s.
   • They do, so a 3x3 square with all borders of 1 is found.
3. Result:
   • The area is 3 x 3 = 9.

If the grid were missing a 1 on the border, the algorithm would automatically check smaller squares until it finds the largest valid one.

Time and Space Complexity

• Brute-force:
  • For each possible square (O(m²n²)), you would check all four borders, which is O(k) for side length k, resulting in a very high total complexity.
• Optimized (Dynamic Programming):
  • Precomputing horizontal and vertical counts: O(mn).
  • For each cell, checking up to O(min(m, n)) possible squares, but since the check is fast (just a few lookups), the total time is O(mn * min(m, n)).
  • Space: O(mn) for the DP matrices.

The optimized approach is efficient and suitable for large grids.

Summary

The problem of finding the largest 1-bordered square in a grid can be solved efficiently by precomputing the number of consecutive 1s horizontally and vertically at each cell. This allows for quick verification of square borders, turning what could be a slow brute-force search into a fast dynamic programming solution. The elegance of this method lies in its use of extra space to save time, and its generalizability to similar "bordered" problems.