How do you solve Largest 1-Bordered Square on LeetCode?

Largest 1-Bordered Square (LeetCode #1139) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n²) time complexity and O(n) space complexity. Key insight: Understanding how to check borders efficiently can save time.

What is the brute force solution for Largest 1-Bordered Square?

The brute force approach for Largest 1-Bordered Square is Brute Force, with O(n²) time complexity and O(1) space complexity. The brute force approach checks every possible square subgrid in the matrix to see if it has all 1s on its border. This is straightforward but inefficient, as it involves checking each square individually. The optimal Optimal Solution approach improves this to O(n²).

What algorithm or data structure is used to solve Largest 1-Bordered Square?

Largest 1-Bordered Square uses the following concepts: Array, Dynamic Programming, Matrix. The recommended patterns to study are: Dynamic Programming, Matrix Traversal.

What are the interview tips for Largest 1-Bordered Square?

Explain your thought process clearly while coding. Consider edge cases and test your code with different inputs. Don't forget to optimize if you start with a brute force solution.

What are common mistakes when solving Largest 1-Bordered Square?

Not checking all borders of the square properly. Failing to handle edge cases like small grids.

#1139

Largest 1-Bordered Square

Medium

ArrayDynamic ProgrammingMatrixDynamic ProgrammingMatrix Traversal

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(n²)
Space	O(1)	O(n)

💡

Intuition

Time O(n²)Space O(n)

The optimal solution utilizes dynamic programming to precompute the number of consecutive 1s in each direction (up, left, down, right) for each cell. This allows us to efficiently check the borders of potential squares without redundant checks.

⚙️

Algorithm

4 steps

1Step 1: Create four auxiliary matrices to store the count of consecutive 1s in the up, left, down, and right directions for each cell.
2Step 2: Fill these matrices by iterating through the grid.
3Step 3: Iterate through each cell again to determine the maximum size of a square that can be formed with that cell as the bottom-right corner.
4Step 4: For each potential square, check if the borders are valid using the precomputed matrices.

solution.py26 lines

1def largest1BorderedSquare(grid):
2    if not grid:
3        return 0
4    rows, cols = len(grid), len(grid[0])
5    up = [[0] * cols for _ in range(rows)]
6    left = [[0] * cols for _ in range(rows)]
7
8    # Fill up and left matrices
9    for r in range(rows):
10        for c in range(cols):
11            if grid[r][c] == 1:
12                up[r][c] = up[r - 1][c] + 1 if r > 0 else 1
13                left[r][c] = left[r][c - 1] + 1 if c > 0 else 1
14
15    max_size = 0
16    # Check for the largest square
17    for r in range(rows):
18        for c in range(cols):
19            if grid[r][c] == 1:
20                size = min(up[r][c], left[r][c])
21                while size > 0:
22                    if up[r][c - size + 1] >= size and left[r - size + 1][c] >= size:
23                        max_size = max(max_size, size)
24                        break
25                    size -= 1
26    return max_size * max_size

ℹ

Complexity note: The time complexity remains O(n²) due to the need to fill the matrices and check for squares. The space complexity is O(n) because we store additional matrices for up and left counts, which is proportional to the size of the input grid.

1Understanding how to check borders efficiently can save time.
2Dynamic programming can help reduce redundant calculations.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.