201. Maximal Square
You're given a binary grid grid with rows rows and cols columns; every cell is the character '0' or '1'. Somewhere in that grid hides the biggest axis-aligned square consisting purely of '1' cells — your job is to find it and return its area (side × side). If the grid holds no '1' at all, return 0.
Only squares count: a 2×4 patch of ones contributes a 2×2 square, not the whole rectangle. The classic insight is local: if you know the biggest square ending at a cell's top, left, and top-left neighbors, the biggest square ending at the cell itself follows in O(1).
Example 1:
Input: grid = ["10100", "10111", "11111", "10010"]
Output: 4
Explanation: The best square is 2×2 — for instance rows 1–2, columns 2–3 are all ones. No 3×3 all-ones square exists, so the area is 4.
Example 2:
Input: grid = ["01", "10"]
Output: 1
Explanation: The ones are isolated on the diagonal, so the largest square is a single cell: area 1.
Example 3:
Input: grid = ["0"]
Output: 0
Explanation: A grid with no ones has no square at all — the answer is 0.
Constraints:
- 1 ≤ rows, cols ≤ 300
- grid[r][c] is '0' or '1'
Hints:
Brute force works: treat every cell as a potential top-left corner and grow the square until a 0 appears. Count what that costs before optimizing.
Define dp[r][c] = the side of the largest all-ones square whose bottom-right corner is (r, c). What do the neighbors above, to the left, and diagonally up-left tell you?
If grid[r][c] is '1', then dp[r][c] = 1 + min(dp[r-1][c], dp[r][c-1], dp[r-1][c-1]) — the square is capped by its weakest supporting direction.
Each dp row only reads the row above it, so two rows (or one row plus a diagonal variable) are enough: O(cols) extra space.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: grid = ["10100", "10111", "11111", "10010"]
Expected output: 4