Largest 1 Bordered Square - Leetcode Solution

Problem Statement: Given a 2D grid of 0's and 1's, find the largest square that has all 1's on its border and is formed by 1's inside the square.

Input: The input is a two-dimensional grid composed of 0's and 1's. The matrix has dimensions n x m.

Output: Return the area of the largest square that satisfies the condition.

Example:

Input: [[1,1,1], [1,0,1], [1,1,1]]

Output: 9

Solution: To solve this problem we can use dynamic programming. We can define a 2D dp array where dp[i][j][0] represents the length of the top border ending at (i, j) and dp[i][j][1] represents the length of the left border ending at (i, j). Then we can iterate through each cell of the input matrix and check whether it can form a square with the borders.

Let's define a variable ans which will keep track of the maximum square area. We will iterate through each cell (i, j) and for each cell, we will calculate the length of the left border dp[i][j][1] and top border dp[i][j][0]. Then we will take the minimum of both lengths and subtract one from it (to account for the corner cell) to get the possible side length of the square that can be formed by this cell. We can then check if this square's borders are all 1's or not. If they are, then we can update the ans variable with the square's area (side * side). We continue this process for all cells, and the final answer will be stored in the ans variable.

The time complexity of this algorithm is O(n*m) as we traverse the input matrix only once.

Python Code:

class Solution:

def largest1BorderedSquare(self, grid: List[List[int]]) -> int:

    n = len(grid)
    m = len(grid[0])
    
    dp = [[[0]*2 for j in range(m)] for i in range(n)]
    
    ans = 0
    
    for i in range(n):
        for j in range(m):
            
            if grid[i][j]==1:
                
                # top border
                dp[i][j][0] = 1 if i==0 else dp[i-1][j][0]+1
                
                # left border
                dp[i][j][1] = 1 if j==0 else dp[i][j-1][1]+1
                
                # check square
                side = min(dp[i][j][0],dp[i][j][1])
                
                while side>0:
                    if dp[i][j-side+1][0]>=side and dp[i-side+1][j][1]>=side:
                        break
                    side -= 1
                
                ans = max(ans,side*side)
    
    return ans

This solution uses a nested list comprehension to initialize the 3D dp array with initial values 0. Then we iterate through each cell and update the dp array based on the current cell's top and left borders. Finally, we update the ans variable if we find a valid square.

1