LeetCode Solutions Blog

Maximal Square

Number: 221

Difficulty: Medium

Paid? No

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

Use dynamic programming to build a solution where each cell in the DP table represents the side length of the largest square ending at that cell.
If the current cell is '1', its DP value is the minimum of the top, left, and top-left neighbors plus one.
Update a global maximum side length during the process to determine the area.
The square's area is the square of its maximum side length.

Space and Time Complexity

Time Complexity: O(m * n), where m is the number of rows and n is the number of columns. Space Complexity: O(m * n) for the DP table (this can be optimized to O(n) with space reduction techniques).

Solution

We use a two-dimensional dynamic programming approach. We define a DP matrix with one extra row and column to simplify boundary conditions. For each cell (i, j) in the input matrix, if the value is '1', then we calculate the DP value as the minimum of its top, left, and top-left neighboring DP values plus one. This value represents the side length of the square ending at (i, j). We also keep track of the maximum side length found and finally compute the area of the maximal square by squaring the maximum side length.

Code Solutions

# Python implementation of the Maximal Square problem

def maximalSquare(matrix):
    # Check if matrix is empty
    if not matrix or not matrix[0]:
        return 0
    rows = len(matrix)
    cols = len(matrix[0])
    # DP table with extra row and col for ease of boundary conditions
    dp = [[0] * (cols + 1) for _ in range(rows + 1)]
    max_side = 0
    # Traverse through each cell in the matrix
    for i in range(1, rows + 1):
        for j in range(1, cols + 1):
            # If the current cell is '1'
            if matrix[i - 1][j - 1] == '1':
                # Compute the minimum value among the top, left, and top-left neighbors and add 1
                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])
    # The area of the square is the square of the side length
    return max_side * max_side

# Example usage:
matrix = [
    ["1", "0", "1", "0", "0"],
    ["1", "0", "1", "1", "1"],
    ["1", "1", "1", "1", "1"],
    ["1", "0", "0", "1", "0"]
]
print(maximalSquare(matrix))