#221

Medium

auto_awesomeState transition dynamic programming

LeetCode Problem Workspace

Maximal Square

Maximal Square is a matrix-based dynamic programming problem that focuses on finding the largest square filled with 1's.

array dynamic programming matrix

Problem Statement

Given a binary matrix of size m x n filled with 0's and 1's, find the largest square that can be formed by 1's. Return the area of this square.

For example, consider the matrix [["1","0","1","0","0"], ["1","0","1","1","1"], ["1","1","1","1","1"], ["1","0","0","1","0"]]. The largest square of 1's has an area of 4.

Examples

Example 1

Input: matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]

Output: 4

Example details omitted.

Example 2

Input: matrix = [["0","1"],["1","0"]]

Output: 1

Example details omitted.

Example 3

Input: matrix = [["0"]]

Output: 0

Example details omitted.

Constraints

m == matrix.length
n == matrix[i].length
1 <= m, n <= 300
matrix[i][j] is '0' or '1'.

Solution Approach

State Transition Dynamic Programming

The problem is solved by maintaining a dynamic programming (DP) matrix where each cell stores the size of the largest square that can end at that position. Transition between states involves checking the left, top, and diagonal cells and taking the minimum of the three plus one, which ensures the square grows optimally.

Iterating through the Matrix

Start iterating through each cell in the matrix. If the cell contains a 1, update the DP matrix by using the values from the previous row, column, and diagonal. If the cell contains a 0, continue with the next iteration, as no square can end at that position.

Final Result Computation

The maximum value in the DP matrix represents the side length of the largest square. Squaring this value gives the area, which is the final answer.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(m * n) where m and n are the dimensions of the matrix, as each cell is processed once. Space complexity can be optimized to O(n) by keeping only the current and previous rows of the DP matrix, reducing the overall space usage from O(m * n).

What Interviewers Usually Probe

Assess the candidate's ability to optimize space in dynamic programming solutions.
Evaluate how well the candidate explains and uses state transitions in dynamic programming.
Check if the candidate can identify the trade-offs between time and space complexities.

Common Pitfalls or Variants

Common pitfalls

Forgetting to initialize the first row and first column of the DP matrix correctly.
Using a brute force approach to check every potential square without leveraging dynamic programming.
Not optimizing space by reducing the DP matrix to only necessary rows.

Follow-up variants

Modify the problem to find the largest square of 1's within a submatrix of the matrix.
Consider a version where the matrix size can vary during runtime or input.
Challenge the candidate to solve the problem without using dynamic programming for a brute force solution.

FAQ

What is the core pattern used to solve the Maximal Square problem?

The problem is primarily solved using state transition dynamic programming, where each matrix cell tracks the largest square that can end at that position.

Can the Maximal Square problem be solved without dynamic programming?

While it's possible to solve it with brute force, dynamic programming offers an efficient solution, reducing time complexity from O(m * n^2) to O(m * n).

How do you optimize space in Maximal Square's solution?

Space can be optimized by storing only the current and previous rows of the DP matrix, reducing space complexity from O(m * n) to O(n).

What happens if the matrix contains all 0's in the Maximal Square problem?

If the matrix consists solely of 0's, the largest square will have an area of 0, as no 1's are available to form a square.

What is the expected output for a 1x1 matrix in the Maximal Square problem?

For a 1x1 matrix, the output will either be 0 or 1, depending on whether the single cell contains a 0 or 1.

terminal

Solution

Solution 1: Dynamic Programming

We define $dp[i + 1][j + 1]$ as the maximum square side length with the lower right corner at index $(i, j)$. The answer is the maximum value among all $dp[i + 1][j + 1]$.

1

2

3

4

5

6

7

8

9

10

11

class Solution:
    def maximalSquare(self, matrix: List[List[str]]) -> int:
        m, n = len(matrix), len(matrix[0])
        dp = [[0] * (n + 1) for _ in range(m + 1)]
        mx = 0
        for i in range(m):
            for j in range(n):
                if matrix[i][j] == '1':
                    dp[i + 1][j + 1] = min(dp[i][j + 1], dp[i + 1][j], dp[i][j]) + 1
                    mx = max(mx, dp[i + 1][j + 1])
        return mx * mx

Continue Practicing

#329 longest increasing path in a matrix #85 maximal rectangle #64 minimum path sum