436. The Largest Square of Ones

A grid holds 0s and 1s. Print the AREA of the largest square made entirely of 1s, or 0 if there is no 1 at all.

Checking every square costs O(r * c * min(r,c)^3) and is hopeless at 300 by 300.

Let side[i][j] be the side of the largest all-ones square whose BOTTOM-RIGHT corner is at (i, j). Fixing the corner is what makes the recurrence possible:

grid[i][j] == 0 -> side[i][j] = 0 otherwise -> side[i][j] = 1 + min( side[i-1][j], side[i][j-1], side[i-1][j-1] )

The min of THREE neighbours is the whole content of the problem, and it is worth convincing yourself rather than accepting. A square of side k ending here needs a square of side k-1 ending directly above, one ending directly left, AND one ending diagonally up-left. Any of the three being smaller caps the result, and the diagonal one is the neighbour people leave out: without it, an L shape of ones is mistaken for a filled square.

Filling rows top to bottom and columns left to right means all three neighbours are already final, which is why this is tabulation and not recursion.

The answer is the largest side ANYWHERE in the table, squared, not the bottom-right entry.

Problem 534 builds this exact table and SUMS every entry instead of taking the maximum, which counts all the all-ones squares of every size rather than measuring the biggest one. The reason that works is a small proof worth seeing once you have this table straight: an entry of s means exactly s squares end at that cell. On the 4 by 5 grid in the first test here, this problem answers 4 and that one answers 15.

Constraints - `1 ≤ r, c ≤ 300` - Every value is `0` or `1`.