Maximal Square

Dynamic Programming2D Matrix

MediumLeetCode #221

30 min

Problem Statement

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

Example

Example 1:

Output: 4

Solution

This problem can be solved efficiently using dynamic programming. We'll create a DP grid, `dp`, where `dp[i][j]` represents the side length of the largest square of '1's whose bottom-right corner is at `matrix[i-1][j-1]`.

If `matrix[i-1][j-1]` is '1', the side length of the square ending at this cell is determined by the minimum side length of the squares ending at its top, left, and top-left diagonal neighbors, plus one. This is because a square can only be formed if all four corners are part of a square of '1's.

Algorithm Steps (DP)

Create a DP grid of size `(m+1) x (n+1)` initialized to 0s.
Initialize a `maxSide` variable to 0 to track the maximum square side length found.
Iterate through the matrix from `(1, 1)` to `(m, n)`.
If `matrix[i-1][j-1]` is '1':
`dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])`.
Update `maxSide = max(maxSide, dp[i][j])`.
The final answer is `maxSide * maxSide`.

Maximal Square DP Grid

Max Square Side: 0

Progress1 / 1

Ready to start.

Maximal Square (DP)


class Solution:
    def maximalSquare(self, matrix: list[list[str]]) -> int:
        if not matrix:
            return 0
        
        m, n = len(matrix), len(matrix[0])
        dp = [[0] * (n + 1) for _ in range(m + 1)]
        max_side = 0
        
        for i in range(1, m + 1):
            for j in range(1, n + 1):
                if matrix[i-1][j-1] == '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])
                    
        return max_side * max_side