Maximal Square

The key idea

Let dp[i][j] be the side length of the largest all-1 square whose bottom-right corner sits at (i, j). A cell can only extend a square if its top, left, and top-left neighbors all already support one — so the square it caps is limited by the smallest of those three: dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1 when matrix[i][j] is '1', else 0. The answer is the largest side seen, squared.

Problem

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

Each matrix[i][j] is the character '0' or '1'. The square must be axis-aligned and made up entirely of '1' cells.

Constraints

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

Examples

Input: matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]] Output: 4

Input: matrix = [["0","1"],["1","0"]] Output: 1

Input: matrix = [["0"]] Output: 0

Complexity

Time: O(m * n) Space: O(n)

See the full solution

✓Full worked approach
✓Reference code in 5 languages
✓Problem-solving tips
✓Step-by-step animated visualization

410310

Step-by-step visualization

Start free →