Problem Overview

Given a binary matrix containing only '1's and '0's, find the largest square or rectangle containing only '1's and return its area.

This problem has two parts:

• Maximal Square: Find the largest square (width = height)

• Maximal Rectangle: Find the largest rectangle (width can differ from height)

Both problems require dynamic programming techniques but use different approaches.

Example: Maximal Square

` matrix = [ ["1","0","1","0","0"], ["1","0","1","1","1"], ["1","1","1","1","1"], ["1","0","0","1","0"] ]

maximalSquare(matrix) # Returns 4

The largest square is 2x2:

["1","1"]

["1","1"]

Area = 2 × 2 = 4

`

Example: Maximal Rectangle

` matrix = [ ["1","0","1","0","0"], ["1","0","1","1","1"], ["1","1","1","1","1"], ["1","0","0","1","0"] ]

maximalRectangle(matrix) # Returns 6

The largest rectangle is 2x3:

Rows 1-2, Columns 2-4

["1","1","1"]

["1","1","1"]

Area = 2 × 3 = 6

`

Constraints

• m == matrix.length

• n == matrix[i].length

• 1 <= m, n <= 300