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

Maximal Square

Difficulty: Medium

Problem Description

Given an m x n binary matrix filled with 0's and 1's, find the largest square containing only 1's and return its area.

Key Insights

  • The problem can be solved using dynamic programming.
  • A square can only be formed if its top, left, and top-left neighbors are also part of a square.
  • We can maintain a DP table where each entry represents the side length of the largest square that can be formed with the cell as its bottom-right corner.

Space and Time Complexity

Time Complexity: O(m * n)
Space Complexity: O(m * n) (or O(n) if using an optimized approach)

Solution

To solve the problem, we utilize a dynamic programming approach. We create a DP table where each cell (i, j) holds the size of the largest square that can be formed with the bottom-right corner at (i, j). The value of each cell in the DP table is computed based on the values of its neighboring cells:

  • If the cell (i, j) contains '1', then dp[i][j] will be the minimum of the three neighboring cells (top, left, and top-left) plus one.
  • If the cell contains '0', then dp[i][j] will remain 0.

Finally, the area of the largest square can be calculated as the square of the maximum value found in the DP table.

Code Solutions

def maximalSquare(matrix):
    if not matrix:
        return 0
    
    m, n = len(matrix), len(matrix[0])
    dp = [[0] * n for _ in range(m)]
    max_side = 0
    
    for i in range(m):
        for j in range(n):
            if matrix[i][j] == '1':
                if i == 0 or j == 0:  # first row or first column
                    dp[i][j] = 1
                else:
                    dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1
                max_side = max(max_side, dp[i][j])
    
    return max_side * max_side
← Back to All Questions