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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Largest 1-Bordered Square

Number: 1239

Difficulty: Medium

Paid? No

Companies: Samsung

Problem Description

Given a 2D grid of 0s and 1s, find the largest square subgrid such that every cell on its border is 1. Return the number of elements in that square (i.e. side_length^2), or 0 if no such subgrid exists.

Key Insights

  • A valid square exists if its entire border (top, bottom, left, right) is filled with 1s.
  • Precompute the number of consecutive 1s to the left and above each cell.
  • Use dynamic programming to quickly check if a border segment of a candidate square is entirely 1s.
  • Iterate from the larger possible square size downwards to return early upon discovering the maximal square.

Space and Time Complexity

Time Complexity: O(n * m * min(n, m)) where n and m are the dimensions of the grid. Space Complexity: O(n * m) for the auxiliary left and up matrices.

Solution

We precompute two DP matrices:

  • One (left) that counts the number of consecutive 1s to the left of and including the current cell.
  • Another (up) that counts the consecutive 1s upwards. For every cell considered as the bottom-right corner of a potential square, the maximum possible side length is limited by the minimum value from these matrices at that cell. We then check if the corresponding top border and left border meet the requirement using the DP matrices. By iterating downward from the maximum possible size, we can update the largest found valid square, ensuring that we return its area immediately once identified.

Code Solutions

def largest1BorderedSquare(grid):
    if not grid or not grid[0]:
        return 0

    rows, cols = len(grid), len(grid[0])
    # Initialize DP arrays for consecutive ones to the left and upwards.
    left = [[0] * cols for _ in range(rows)]
    up = [[0] * cols for _ in range(rows)]
    
    # Precompute DP states.
    for i in range(rows):
        for j in range(cols):
            if grid[i][j] == 1:
                left[i][j] = (left[i][j-1] if j > 0 else 0) + 1
                up[i][j] = (up[i-1][j] if i > 0 else 0) + 1
    
    max_side = 0
    # Check every cell as potential bottom-right corner of a square.
    for i in range(rows):
        for j in range(cols):
            # Determine the maximum possible square side at (i, j)
            side = min(left[i][j], up[i][j])
            while side > max_side:
                # Validate top border and left border for the candidate square.
                if up[i][j - side + 1] >= side and left[i - side + 1][j] >= side:
                    max_side = side
                side -= 1
    
    return max_side * max_side

# Example usage:
print(largest1BorderedSquare([[1,1,1],[1,0,1],[1,1,1]]))  # Expected output: 9
print(largest1BorderedSquare([[1,1,0,0]]))                 # Expected output: 1
← Back to All Questions