Maximal Square
Medium · Matrix · Array · Dynamic Programming · Matrix
Problem
You are given an m x n binary matrix whose cells are the characters '0' and '1'.
Return the area of the largest square block made entirely of '1's. If there is no '1' at all, return 0.
Examples
Input: matrix = [["1","1","0"],["1","1","1"],["0","1","1"]] Output: 4
Two different 2 x 2 blocks of ones exist, but no 3 x 3, so the area is 4.
Input: matrix = [["0","1"],["0","0"]] Output: 1
Only a single 1 exists, giving area 1.
Input: matrix = [["0","0","0"]] Output: 0
There are no ones, so the area is 0.
Constraints
- m == len(matrix), n == len(matrix[i])
- 1 <= m, n <= 300
- matrix[i][j] is '0' or '1'
Approaches
- Baseline: grow a square from every cell — time O(m · n · min(m, n)²), space O(1)
Follow-up
Return the largest all-ones rectangle instead of a square. The min-of-three trick no longer works; treat each row as the base of a histogram of column heights and use a monotonic stack per row, for O(m · n) in total.
Related problems
Start free on Cariara · Coding problems · System design studio
