How to solve largest 1-bordered square problem in Python

Key takeaways:
The largest 1-bordered square problem involves finding the largest square in a 2D grid where 1s form its outer border.
Use dynamic programming with two auxiliary 2D arrays to track consecutive 1s in both directions.
Iterate over square sizes and check if all four borders have enough consecutive 1s.
Return the size of the largest square that satisfies the border condition.
The time complexity is $O(m * n * min(m, n))$ , where $m$ is rows, and $n$ is columns.
The space complexity is $O(m * n)$ due to two 2D arrays used for tracking consecutive 1s.

The largest 1-bordered square problem is useful in image processing, computer vision, and pattern recognition tasks, where detecting specific shapes or boundaries within a grid or image is essential. It also applies to solving spatial problems in game development, urban planning, or grid-based simulations where identifying structured areas with distinct borders is critical for optimization or design.

In the largest 1-bordered square problem, we have a 2D grid consisting of 0s and 1s. We have to determine the size of the largest square-shaped subgrid, with 1s forming its entire outer border. If no such subgrid exists in the grid, we have to return 0.

Algorithm to solve the largest 1-bordered square problem

The algorithm for this problem is as follows:

Get the dimensions of the grid (number of rows and columns):
1. Store the number of rows and columns in the grid in rows variable and cols variable.
Create two 2D arrays to track the count of consecutive 1s:
1. Define two 2d arrays (above, left) to keep track of consecutive 1s in those directions for each cell and populate them based on the input grid. Dynamic programming (DP) approach is implemented here through the two arrays, left and above. These arrays store intermediate results to avoid redundant calculations when checking for the borders of potential 1-bordered squares.
Populate the arrays based on the input grid:
1. If a cell in the grid contains 1, increase the count of consecutive 1s for both arrays from the left and above (respectively).
2. If the cell contains 0, set the counts to 0 in both arrays for that cell.
Check all possible square sizes:
1. Start from the smallest dimension of the grid and iterate downwards to 1.
Check if a square of the current size can be formed:
1. For each potential square, verify that all four borders of the square have at least the number of 1s equal to the current square size.
Update the largest square size:
1. If all borders meet the condition, update the largest square size to the current square size.
Return the largest square size:
1. After checking all possible sizes, return the largest square size found. If no valid square is found, return 0.

def largest1BorderedSquare(grid):
    rows = len(grid)
    cols = len(grid[0])
    left = [[0] * cols for _ in range(rows)]
    above = [[0] * cols for _ in range(rows)]
    for row in range(rows):
        for col in range(cols):
            if grid[row][col] == 1:
                left[row][col] = 1 if col == 0 else left[row][col - 1] + 1
                above[row][col] = 1 if row == 0 else above[row - 1][col] + 1
    largest = 0
    for side in range(min(rows, cols), 0, -1):
        for row in range(rows - side + 1):
            for col in range(cols - side + 1):
                if (
                    left[row][col + side - 1] >= side
                    and left[row + side - 1][col + side - 1] >= side
                    and above[row + side - 1][col] >= side
                    and above[row + side - 1][col + side - 1] >= side
                ):
                    return side * side
    return largest
grid = [[1, 1, 1], [1, 0, 1], [1, 1, 1]]
result = largest1BorderedSquare(grid)
print("The size of the largest 1-bordered square is:", result)

This code can be explained as follows:

Line 1: Define the largest1BorderedSquare function that takes a 2D grid as a parameter and calculates the largest 1-bordered square inside the grid.
Lines 2–3: Define two variables to store the number of rows and columns in grid.
Lines 5–6: Define two 2D arrays, left and above, which are initialized with all elements set to 0. These arrays will keep track of the consecutive 1s to the left and above each cell in the grid.
Lines 8–9: Iterate through each cell in the grid using two nested loops (for row and col).
Lines 10–12: If the current cell in grid contains a 1:
- Calculate the number of consecutive 1s to the left of the cell and store it in the corresponding position in the left array. This is done by checking if col is 0 and using an if statement to either set it to 1 (if it’s the first column) or add 1 to the value in the cell to the left.
- Calculate the number of consecutive 1s above the cell and stores it in the corresponding position in the above array. This is done the same way as above; this time replacing col with row.
Line 14: Define largest, which will contain the value of the largest 1-bordered square inside the grid.
Lines 16–18: Use nested loops to explore different square sizes (side) starting from the minimum of rows and cols down to 1.
Lines 19–24: Check four conditions to determine if the square with the current side is a 1-bordered square. We check the consecutive 1s to the left, right, above, and below the square to ensure that 1s border all sides.
Line 25: Return the area of the square if the conditions have been met.
Line 27: Return the value of largest.
Lines 29–31: Code to call our function.

Time complexity

The above code example has a time complexity of $O(m*n \cdot \min(m, n))$ , where $m$ is the number of rows in the grid and n is the number of columns. Thus, $min⁡(m,n)$ represents the upper limit on the side length of squares being considered and contributes to the number of checks required in the worst case.

Space complexity

The code given above has the space complexity of code above is $O(m \times n)$ since we’re creating two additional 2D arrays, left and right. so each of size $m \times n$ to store the consecutive 1s to the left and above each cell. The space taken by these arrays is $O (m\times n)$ for each.

Note: You may alter the code at the end to test with your own values.

Quiz

Let’s assess your understanding by answering the questions below:

Free Resources

How to solve largest 1-bordered square problem in Python

Algorithm to solve the largest 1-bordered square problem

Python code to the largest 1-bordered square solution

Time complexity

Space complexity

Quiz