Maximal Square
Hard · rating 1900 · Dynamic Programming, Matrix
The first line has r and c. The next r lines are strings of c characters (0 or 1). Print the area of the largest square that contains only 1s.
Constraints: 1 ≤ r, c ≤ 500
Editorial
Approach
Let dp[i][j] be the side length of the largest all-ones square whose bottom-right corner is cell (i, j). If the cell is 1, it can extend the squares ending directly above, to the left, and up-left — but only as far as the smallest of those three allows, plus one.
The min is the bottleneck
A square of side k here needs squares of side k-1 in all three neighbouring directions; the weakest neighbour caps the size.
if grid[i-1][j-1] == '1':
dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1
best = max(best, dp[i][j])Complexity
Time: O(r·c). Space: O(r·c) (reducible to O(c)).
Related problems
- Treasure Grid — Hard
- Minimum Path Sum — Hard
- Longest Common Substring — Hard
- Balanced Bracket Count — Hard
- Equal Subset Partition — Hard
- Word Break — Hard