AlgoViz
HomeDynamic Programming

Maximal Square

Medium

The same recurrence, take the maximum

Problem

Return the area of the largest square of all 1s in a binary matrix.

In simple words

Each cell's biggest square depends on the smallest square among its top, left, and top-left neighbours.

The idea

Each cell holds the side of the largest all-ones square ending there, computed as one plus the minimum of its three neighbours. The answer is the largest side squared.

The trick

  • The minimum of three neighbours is what forces squareness.
  • Track the maximum side while filling; square it at the end.

This one walks through the worked example rather than tracing the algorithm frame by frame — a full walkthrough is still to be drawn. The code and the idea below are the real solution.

1
0
1
0
0
0
1
2
3
4

Step 1 of 2. Here's the example — [[1,0,1,0,0],[1,0,1,1,1],[1,1,1,1,1],[1,0,0,1,0]] Values: 1, 0, 1, 0, 0.

1/2
Optimal
timeO(m*n)spaceO(n)
1dp[i][j]=grid==1 ? 1+min(dp up,left,up-left) : 02return max(dp)^2

Input

array
[1, 0, 1, 0, 0]

Output

answer
—

Check yourself

3 quick questions about this walkthrough. A wrong answer costs nothing.

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
Explanation:
The biggest all-1 square has area 4.

Example 2

Input:
matrix = [[0,1],[1,0]]
Output:
1
Explanation:
Only single 1s → area 1.

Example 3

Input:
matrix = [[0]]
Output:
0
Explanation:
No 1s → 0.

Practice this problem:LeetCode(opens in a new tab)Search GeeksforGeeks(opens in a new tab)

Finished the walkthrough? Add it to your streak.