LeetCode #221 Medium

Maximal Square

Given a binary matrix, find the largest square containing only 1s and return its area.

dynamic-programmingmatrixgrid

02

Intuition

💡

Checking every candidate square is O((mn)^2). The reframe that fixes it: let dp[i][j] be the side length of the largest all-1 square whose bottom-right corner is exactly (i,j). Anchoring on a corner turns a two-dimensional search into a single value per cell. And that value has a clean recurrence — to build a square of side k ending here, the squares ending directly above, directly left, and diagonally up-left must each have side at least k-1, so the minimum of those three, plus one, is the answer.

03

Approach

1

Anchor squares at their bottom-right corner

The difficulty with 'largest square' is that a square is defined by a corner and a size, so brute force explores both. Fixing the bottom-right corner removes one dimension: for each cell, ask only 'what is the biggest square that ends here?' Every square in the grid ends at exactly one cell, so scanning all cells and taking the maximum covers every candidate without repetition.

2

Derive the min-of-three recurrence

Suppose dp[i][j] = k, meaning a k x k all-1 square ends at (i,j). Removing its last row leaves a (k-1) x (k-1) square ending at (i-1,j); removing its last column leaves one ending at (i,j-1); removing both leaves one at (i-1,j-1). So all three neighbours must support at least k-1. Conversely, if all three support k-1 and the cell itself is a 1, a k x k square exists. Hence dp[i][j] = 1 + min(top, left, diagonal). It is the minimum, not the maximum — one weak neighbour caps the whole square, and that is the insight the problem turns on.

3

Fill the grid and track the best

Cells holding 0 get dp = 0. Cells on the top row or left column can only ever anchor a 1 x 1 square, since there is nothing above or to the left to extend into. Everything else uses the recurrence. Track the running maximum side as you fill, and return its square, because the problem asks for area rather than side length — an easy point to lose. One pass, O(mn).

04

Solution & live demo

python

▶1class Solution:
▶2    def maximalSquare(self, matrix):
▶3        R, C = len(matrix), len(matrix[0])
▶4        dp = [[0] * C for _ in range(R)]
▶5        best = 0
▶6        for i in range(R):
▶7            for j in range(C):
▶8                if matrix[i][j] == 0:
▶9                    continue
▶10                if i == 0 or j == 0:
▶11                    dp[i][j] = 1
▶12                else:
▶13                    dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])
▶14                best = max(best, dp[i][j])
▶15        return best * best

05

Edge cases

No 1s in the matrix

Every dp entry is 0, the running maximum stays 0, and the area returned is 0.

Single row or single column

Every cell is on a border, so the largest square is 1 x 1 wherever a 1 appears, giving area 1.

Entire matrix is 1s

The recurrence grows the side steadily and the answer is min(m, n) squared.

Returning the side instead of the area

The most common mistake. Remember to square the tracked side before returning.

06

Complexity

Time

O(m x n)

Space

O(m x n)

The table can be reduced to a single row plus one saved diagonal value for O(n) space, since each cell reads only the previous row and the cell to its left.