We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Largest 1-Bordered Square

Difficulty: Medium

Problem Description

Given a 2D grid of 0s and 1s, return the number of elements in the largest square subgrid that has all 1s on its border, or 0 if such a subgrid doesn't exist in the grid.

Key Insights

  • A square subgrid must have all its border elements equal to 1.
  • The problem can be solved using dynamic programming to track the size of the largest square ending at each cell.
  • We need to check the borders of potential squares to ensure they are filled with 1s.

Space and Time Complexity

Time Complexity: O(n * m), where n is the number of rows and m is the number of columns in the grid. Space Complexity: O(n * m) for the dynamic programming table used to store intermediate results.

Solution

The solution employs a dynamic programming approach where we maintain a DP table to track the size of the largest square that can be formed with its bottom right corner at each cell. For each cell that contains a 1, we determine the possible size of the square by checking the values in the DP table for the left, top, and top-left diagonal cells. Additionally, we need to validate that the square has all 1s on its border.

Code Solutions

def largest1BorderedSquare(grid):
    if not grid:
        return 0

    n, m = len(grid), len(grid[0])
    dp = [[0] * (m + 1) for _ in range(n + 1)]
    max_size = 0

    for i in range(1, n + 1):
        for j in range(1, m + 1):
            if grid[i - 1][j - 1] == 1:
                dp[i][j] = min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]) + 1
                size = dp[i][j]
                if (i - size + 1 >= 0 and j - size + 1 >= 0 and
                    all(grid[k][j - 1] == 1 for k in range(i - size + 1, i + 1)) and
                    all(grid[i - 1][k] == 1 for k in range(j - size + 1, j + 1))):
                    max_size = max(max_size, size)

    return max_size * max_size
← Back to All Questions