Question
Given a binary matrix containing characters `'0'` and `'1'`, return the area of the largest axis-aligned region containing only ones. ```python def maximal_square(matrix: list) -> int: ... def maximal_rectangle(matrix: list) -> int: ... ``` ## Implementation requirements 1. Implement `maximal_square`. An empty matrix or a matrix containing no ones returns `0`. 2. Extend the solution to `maximal_rectangle`, where height and width may differ. Inputs are rectangular lists of rows containing only the strings `'0'` and `'1'`; empty matrices and zero-column matrices return `0`. Return an integer area without modifying the input. Malformed rows are outside the assessed input contract. Target `O(rows * cols)` time. For the square, aim for `O(cols)` auxiliary space; for the rectangle, explain the monotonic-stack invariant used with row histograms. `_histogram` is an optional implementation helper, not an assessed interface. The provided `run_case` dispatches fixture envelopes to the two assessed functions. ## Design discussion (not graded) 1. Return the coordinates of one maximum region. 2. Process rows as a stream. 3. Handle a sparse matrix whose dimensions are much larger than its number of ones. 4. Support updates to cells followed by repeated queries.