213. Maximum Size Square Sub-Matrix With All 1s

Given a binary matrix, find the area of the largest square sub-matrix consisting entirely of 1s.

Input: The first line contains two integers rows and cols. Each of the next rows lines contains cols space-separated values (0 or 1) representing the binary matrix. Output: Print a single integer - the area of the largest all-1s square sub-matrix.

1 <= rows, cols <= 1000

The DP tracks SIDE LENGTH, not area directly - remembering to SQUARE the maximum dp value found (not just report it directly) at the very end is an easy final step to forget.

Find the area of the largest square sub-matrix made entirely of 1s. Brute force: For every possible square size and every possible top-left position, check if that whole square is all 1s directly - this costs O(rows*cols*min(rows,cols)) or worse, much slower than the DP approach. Optimised: Taking the MINIMUM of the three neighboring dp values (rather than any other combination) is the key insight: a square of side length s ending at (i,j) can only exist if all three adjacent smaller squares (up, left, and diagonally up-left) support AT LEAST a square of side s-1 - the bottleneck neighbor determines how far the current square can extend.

For every cell treated as a potential top-left corner of a square, try increasing side lengths starting at 1, and for each candidate size check whether every cell within that square is 1 by scanning the whole square. Stop growing the size for that corner as soon as a square fails the all-ones check, and track the largest square area found across all corners. This re-examines many overlapping sub-squares repeatedly, making it very expensive. Time: O(rows * cols * min(rows,cols)^3) Space: O(1)

Use the same recurrence as the full DP table, but observe that computing dp[i][j] only ever needs the previous row's values and the current row's values computed so far. Keep just one 1-D array of length cols instead of the full 2-D table, updating it in place while preserving the needed top-left diagonal value in a temporary variable before it gets overwritten. This keeps the same overall work as the full-table version but cuts auxiliary memory down to a single row. Time: O(rows*cols) Space: O(cols)

Build a 2D DP table where dp[i][j] is the side length of the largest all-ones square whose bottom-right corner is at cell (i,j). If the matrix cell is 0, dp[i][j] is 0; otherwise dp[i][j] equals 1 plus the minimum of the three neighboring DP values (top, left, and top-left diagonal), since a bigger square can only extend as far as its most constrained neighbor. The answer is the largest dp value squared, found after filling the whole table in one pass. Time: O(rows*cols) Space: O(rows*cols)

1. dp[i][j] = side length of the largest all-1s SQUARE whose bottom-right corner is at (i,j). 2. If the current cell is 1, dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) - the square can only extend as far as the SHORTEST of its three neighboring squares allows. 3. The answer is the SQUARE of the maximum dp value found anywhere.

Time: O(rows*cols) - filling the DP table, one cell at a time. Space: O(rows*cols) for the full table (reducible to O(cols) with a rolling 1D array, since each row only depends on the row directly above it).

Test a matrix of all 0s (answer 0), a matrix of all 1s, a 1x1 matrix, and rows/cols at the upper bound of 1000.

Be ready to explain WHY the minimum (not maximum or sum) of the three neighbors is the correct combination - a square's side length is limited by its WEAKEST supporting neighbor, exactly analogous to a chain being only as strong as its weakest link.