Why it works
- A k × k square of 1s with its corner at (r, c) contains the (k - 1) × (k - 1) squares ending above, to the left and on the diagonal. So it exists exactly when all three of those cells reach k - 1: dp is 1 + the smallest of them.
- The smallest one is the limit: at (2, 3) the left reaches 3 and the diagonal 2, but up is 1, because the 0 at (0, 3) breaks every bigger square there.
- Row by row, the three cells a cell reads are filled before it, and side keeps the biggest value seen, so the area is side × side at the end.
Complexity
Time O(m × n): each cell reads three neighbours once. Memory O(m × n) for the table; a cell reads only its row and the row above, so two rows are enough.
nextNow solve it yourself, no hints.
Solve on LeetCode ↗