Return the area of the largest square containing only 1s in a binary matrix. Test your code, then compare with the explained solution. Free online practice.

Maximal Square

Binary Tree Preorder Traversal

Decode String

Return the area of the largest square containing only 1s in a binary matrix.

You are given an `m x n` binary matrix `matrix` containing only the integer values `0` and `1` (not characters). Return the area of the largest square that contains only `1`s.

**Input / output**
- Input: `matrix: int[][]`
- Output: `int` (the area of the largest all-`1` square)

**Examples**
1. `matrix = [[1,0,1,0,0],[1,0,1,1,1],[1,1,1,1,1],[1,0,0,1,0]]` returns `4` because the largest all-`1` square has side length `2`.
2. `matrix = [[0,1],[1,0]]` returns `1` because every all-`1` square is only a single cell.
3. `matrix = [[1]]` returns `1`.

**Constraints**
- `1 <= matrix.length, matrix[0].length <= 300`
- `matrix[i][j]` is either `0` or `1`

**Follow-up**
Can you reduce the dynamic-programming space from `O(m*n)` to `O(n)` by keeping only the previous row while preserving the same transition?

- A square is only valid if every cell inside it is `1`.
- The answer asks for **area**, but it is easier to reason about side length first and square it at the end.
- That leads naturally to either expanding candidate squares or building a DP table of best side lengths.

Start from what makes a square valid

- Treat each cell containing `1` as a possible top-left corner.
- Try to grow the square one layer at a time, checking the newly added bottom row and right column before accepting the larger side length.
- This works, but in the worst case it repeatedly rechecks many cells and costs `O(m*n*k^2)` time where `k = min(m, n)`.

Brute force: expand from each top-left 1

- Let `dp[r][c]` be the side length of the largest all-`1` square whose bottom-right corner is `(r, c)`.
- If `matrix[r][c]` is `0`, then `dp[r][c] = 0`.
- Otherwise, border cells can only form a `1x1` square, and interior cells extend the smallest of the three neighboring squares: top, left, and top-left diagonal.

Use DP for squares ending at each cell

- Sweep the matrix row by row.
- When `matrix[r][c] == 1`, compute `dp[r][c] = 1 + min(dp[r-1][c], dp[r][c-1], dp[r-1][c-1])` for interior cells, or `1` on the first row/column.
- Track the largest side length seen, then return its square as the area. This runs in `O(m*n)` time and `O(m*n)` space.