Problem Description

You are given a 2D grid containing only 0s and 1s. Your task is to find the largest square subgrid where all the cells on the border of the square contain 1s. The interior cells can be either 0 or 1 - only the border matters.

For example, if you have a 3×3 square, you need all 8 border cells (the outer frame) to be 1s to consider it valid. The center cell can be anything.

The problem asks you to return the number of elements in the largest such square (which is the area, or side length squared). If no valid square with all 1s on its border exists in the grid, return 0.

Key points to understand:

• You're looking for a square subgrid (not rectangle)
• Only the border cells of the square need to be 1s
• The interior cells don't matter - they can be 0 or 1
• You want the largest possible such square
• Return the total number of cells in that square (side × side)

For instance, a valid 3×3 square bordered by 1s would return 9 (since 3 × 3 = 9).

Intuition

To check if a square has all 1s on its border, we need to verify four sides: top, bottom, left, and right. A naive approach would be to check each cell on the border for every possible square, but this would be inefficient.

The key insight is that we can precompute useful information to speed up our border checks. For any position (i, j) in the grid, if we know:

• How many consecutive 1s extend downward from this position
• How many consecutive 1s extend to the right from this position

Then we can quickly verify if a square's border is valid.

Why does this help? Consider a square with top-left corner at (i, j) and side length k:

• The left side of the square needs k consecutive 1s going down from (i, j) - we can check if down[i][j] >= k
• The top side needs k consecutive 1s going right from (i, j) - we can check if right[i][j] >= k
• The right side needs k consecutive 1s going down from (i, j+k-1) - we can check if down[i][j+k-1] >= k
• The bottom side needs k consecutive 1s going right from (i+k-1, j) - we can check if right[i+k-1][j] >= k

By preprocessing these down and right arrays using dynamic programming (working backwards from bottom-right), we can check any square's validity in O(1) time.

Since we want the largest square, we can enumerate side lengths from largest to smallest. As soon as we find a valid square of side length k, we can immediately return k * k since any larger square would have been found earlier in our search.

Learn more about Dynamic Programming patterns.

Solution Approach

The solution uses prefix sum preprocessing combined with enumeration to efficiently find the largest square with all 1s on its border.

Step 1: Preprocess the grid with prefix sums

We create two 2D arrays:

• down[i][j]: counts consecutive 1s going downward from position (i, j)
• right[i][j]: counts consecutive 1s going to the right from position (i, j)

We fill these arrays by iterating from bottom-right to top-left:

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 each cell with value 1:

• down[i][j] equals 1 + down[i+1][j] (or 1 if at the bottom edge)
• right[i][j] equals 1 + right[i][j+1] (or 1 if at the right edge)

Step 2: Enumerate possible square sizes

We try square sizes from largest to smallest (min(m, n) down to 1):

for k in range(min(m, n), 0, -1):

Step 3: Check all possible positions for each square size

For each square size k, we check all valid top-left corner positions (i, j):

for i in range(m - k + 1):
    for j in range(n - k + 1):

Step 4: Validate the square's border

A square with top-left at (i, j) and side length k has valid borders if:

• Left side: down[i][j] >= k (needs k consecutive 1s going down)
• Top side: right[i][j] >= k (needs k consecutive 1s going right)
• Right side: down[i][j + k - 1] >= k (from top-right corner going down)
• Bottom side: right[i + k - 1][j] >= k (from bottom-left corner going right)

If all four conditions are met, we immediately return k * k since we're checking from largest to smallest.

Time Complexity: O(m * n * min(m, n)) where preprocessing takes O(m * n) and checking all squares takes O(m * n * min(m, n)).

Space Complexity: O(m * n) for the two auxiliary arrays.

Example Walkthrough

Let's walk through finding the largest square with all 1s on its border using this grid:

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

Step 1: Build the preprocessing arrays

We create down and right arrays by working backwards from bottom-right to top-left.

Starting with down (counts consecutive 1s going downward):

• down[2][2] = 1 (bottom-right, only itself)
• down[2][1] = 1 (grid[2][1] = 1, but it's the bottom row)
• down[2][0] = 1 (bottom-left, only itself)
• down[1][2] = 1 + down[2][2] = 2 (grid[1][2] = 1, adds to below)
• down[1][1] = 0 (grid[1][1] = 0, breaks the chain)
• down[1][0] = 1 + down[2][0] = 2 (grid[1][0] = 1, adds to below)
• down[0][2] = 1 + down[1][2] = 3 (all three cells going down are 1s)
• down[0][1] = 1 (grid[0][1] = 1, but grid[1][1] = 0 below)
• down[0][0] = 1 + down[1][0] = 3 (all three cells going down are 1s)

down = [[3, 1, 3],
        [2, 0, 2],
        [1, 1, 1]]

Similarly for right (counts consecutive 1s going rightward):

right = [[3, 2, 1],
         [1, 0, 1],
         [3, 2, 1]]

Step 2: Check squares from largest to smallest

Starting with size k=3 (the maximum possible):

• Check position (0,0) for a 3×3 square:
  • Left side: down[0][0] = 3 >= 3 ✓
  • Top side: right[0][0] = 3 >= 3 ✓
  • Right side: down[0][2] = 3 >= 3 ✓
  • Bottom side: right[2][0] = 3 >= 3 ✓

All four borders are valid! We found a 3×3 square with all 1s on its border.

Return: 3 × 3 = 9

Note that the center cell grid[1][1] = 0 doesn't matter - only the 8 border cells need to be 1s, which they are:

Border cells: [1, 1, 1]
              [1, _, 1]  
              [1, 1, 1]

If this 3×3 square hadn't worked, we would continue checking smaller sizes (k=2, then k=1) until finding a valid square or returning 0 if none exist.

Solution Implementation

Time and Space Complexity

Time Complexity: O(m × n × min(m, n))

The algorithm consists of two main parts:

1. Preprocessing phase: Computing the down and right arrays requires iterating through all cells in the grid once, which takes O(m × n) time.

2. Search phase: The algorithm searches for the largest square by:

   • Iterating through all possible square sizes k from min(m, n) down to 1, which gives us O(min(m, n)) iterations
   • For each square size k, checking all possible top-left positions (i, j) where a square of size k could fit, which requires O((m - k + 1) × (n - k + 1)) iterations
   • Each validity check for a square takes O(1) time

   In the worst case, when no valid square is found until k = 1, the total iterations would be: Σ(k=1 to min(m,n)) (m - k + 1) × (n - k + 1) ≈ O(m × n × min(m, n))

Therefore, the overall time complexity is O(m × n × min(m, n)).

Space Complexity: O(m × n)

The algorithm uses two auxiliary 2D arrays:

• down[m][n]: stores the count of consecutive 1s going downward from each cell
• right[m][n]: stores the count of consecutive 1s going rightward from each cell

Both arrays have dimensions m × n, resulting in a space complexity of O(m × n).

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Confusing Border Validation with Full Square Validation

A common mistake is thinking that checking the four corners' consecutive counts validates the entire border. However, the consecutive count arrays tell us about potential borders, not guaranteed complete borders.

The Pitfall: When we check consecutive_ones_right[top_row][left_col] >= square_size, we're verifying that there are enough consecutive 1s going right from the top-left corner. But this doesn't guarantee that ALL cells on the top border are part of our square - some of those consecutive 1s might extend beyond our square's boundary.

Why This Works Anyway: The algorithm is correct because:

• We check all four corners' consecutive counts
• consecutive_ones_right[top_row][left_col] >= square_size ensures the top border has at least square_size consecutive 1s starting from the left corner
• consecutive_ones_down[top_row][right_col] >= square_size ensures the right border has at least square_size consecutive 1s starting from the top-right corner
• The combination of all four checks guarantees the entire border is made of 1s

2. Off-by-One Errors in Index Calculations

The Pitfall: It's easy to make mistakes when calculating the bottom-right corner indices:

# Incorrect:
bottom_row = top_row + square_size  # This would be one row too far
right_col = left_col + square_size  # This would be one column too far

# Correct:
bottom_row = top_row + square_size - 1
right_col = left_col + square_size - 1

Solution: Remember that if the top-left corner is at (i, j) and the square has side length k, then:

• Top-right corner: (i, j + k - 1)
• Bottom-left corner: (i + k - 1, j)
• Bottom-right corner: (i + k - 1, j + k - 1)

3. Incorrect Preprocessing Direction

The Pitfall: Building the prefix arrays in the wrong direction:

# Incorrect - going from top-left to bottom-right:
for row in range(rows):
    for col in range(cols):
        if grid[row][col] == 1:
            consecutive_ones_down[row][col] = consecutive_ones_down[row - 1][col] + 1  # Wrong!

Solution: The arrays must be built from bottom-right to top-left because:

• consecutive_ones_down[i][j] needs to know about cells below it
• consecutive_ones_right[i][j] needs to know about cells to its right
• We can only compute these if we've already processed those cells

4. Not Handling Edge Cases in Preprocessing

The Pitfall: Forgetting to handle boundary conditions when building prefix arrays:

# Incorrect - might cause index out of bounds:
consecutive_ones_down[row][col] = consecutive_ones_down[row + 1][col] + 1

# Correct - with boundary check:
if row + 1 < rows:
    consecutive_ones_down[row][col] = consecutive_ones_down[row + 1][col] + 1
else:
    consecutive_ones_down[row][col] = 1

Solution: Always check if the next cell exists before accessing it. For cells on the edge, initialize the count to 1 if the cell itself contains a 1.