Approach Summary
dp[i][j] = side length of largest square with bottom-right at (i,j). dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1 if cell is 1.
How to Recognize This Pattern
- "Largest square containing only 1s"
- Min of three neighbours limits the square you can extend
Complexity Analysis
Time Complexity
O(m × n)
Space Complexity
O(m × n)
Tags
Array Dynamic Programming Matrix