How do you solve Maximal Square on LeetCode?

Maximal Square (LeetCode #221) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(m * n) time complexity and O(m * n) space complexity. Key insight: Dynamic programming allows us to build solutions incrementally.

What is the brute force solution for Maximal Square?

The brute force approach for Maximal Square is Brute Force, with O(n²) time complexity and O(1) space complexity. The brute force approach checks every possible square in the matrix to see if it contains only '1's. This is simple but inefficient, as it involves checking many overlapping squares. The optimal Optimal Solution approach improves this to O(m * n).

What algorithm or data structure is used to solve Maximal Square?

Maximal Square uses the following concepts: Array, Dynamic Programming, Matrix. The recommended patterns to study are: Dynamic Programming, Matrix Traversal.

What are the interview tips for Maximal Square?

Explain your thought process clearly. Discuss edge cases, like empty matrices. Be prepared to optimize your solution after discussing the brute force.

What are common mistakes when solving Maximal Square?

Not initializing the DP array correctly. Forgetting to check boundaries when accessing the DP array.

#221

Maximal Square

Medium

ArrayDynamic ProgrammingMatrixDynamic ProgrammingMatrix Traversal

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(m * n)
Space	O(1)	O(m * n)

💡

Intuition

Time O(m * n)Space O(m * n)

The optimal approach uses dynamic programming to build a 2D array that stores the size of the largest square that can end at each cell. This allows us to compute the maximum square size in a single pass through the matrix.

⚙️

Algorithm

3 steps

1Step 1: Create a DP array of the same size as the input matrix initialized to 0.
2Step 2: Iterate through each cell in the matrix; if the cell is '1', update the DP array based on the minimum of the three neighboring squares (top, left, top-left).
3Step 3: Keep track of the maximum value in the DP array, which represents the side length of the largest square.

solution.py15 lines

1def maximalSquare(matrix):
2    if not matrix:
3        return 0
4    max_side = 0
5    rows, cols = len(matrix), len(matrix[0])
6    dp = [[0] * cols for _ in range(rows)]
7    for i in range(rows):
8        for j in range(cols):
9            if matrix[i][j] == '1':
10                if i == 0 or j == 0:
11                    dp[i][j] = 1
12                else:
13                    dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1
14                max_side = max(max_side, dp[i][j])
15    return max_side * max_side

ℹ

Complexity note: The time complexity is O(m * n) because we iterate through each cell once. The space complexity is also O(m * n) due to the DP array storing results for each cell.

1Dynamic programming allows us to build solutions incrementally.
2Understanding the relationship between subproblems is crucial.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.