Dynamic Programming
Medium
Maximal Square
Given an m x n binary matrix filled with 0's and 1's, find the largest square containing only 1's and return its area.
10 min read
Solve on LeetCodeProblem Understanding
We need to find the largest square of 1s.
Example:
1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0
Here, distinct 2x2 squares exist. The largest possible is side length 2. Output area: 4.
Algorithm Strategy
We use DP. dp[i][j] represents the side length of the largest square whose bottom-right corner is at (i, j).
Recurrence:
If matrix[i][j] == '1':dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1
Intuition:
A square of size k ending at (i, j) requires:
- Square of size
k-1ending at top(i-1, j) - Square of size
k-1ending at left(i, j-1) - Square of size
k-1ending at diagonal(i-1, j-1)
Interactive Visualization
Step 1 / 1
Initializing...
1x
See the Logic in Motion
Stop memorizing code. Unlock the full interactive visualizer to master the logic step-by-step.Stop Guessing, Start Mastering.
Build the FAANG intuition. Master this pattern with optimized implementations, visual dry runs, and our curated collection of high-yield problems.