 All Problems
Maximal Square
medium
array
dynamic programming
matrix
amazon
facebook
google

Given an m x n binary matrix filled with 0s and 1s, find the largest square containing only 1s and return its area.

Example 1:

Input:
4 5
1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0
Output: 4

Example 2:

Input:
1 1
0 1
Output: 1

Constraints:

  • m == matrix.length, n == matrix[i].length
  • 1 ≤ m, n ≤ 300
  • matrix[i][j] is '0' or '1'

Input format: First line: m n. Next m lines: n space-separated 0s or 1s.

Output format: Area of the largest square.

Run to check your code against the sample cases, or submit to run every case