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.

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.