Maximal Square

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 1s.

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?