Skip to main content

221. Maximal Square

medium

Given a binary matrix, find the side length of the largest square made entirely of 1s. The recurrence dp[i][j] = 1 + min(top, left, top-left) is one of the most quotable lines in interview DP.

By Sam K., Founder, InterviewChamp.AI · Last verified

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.

Constraints

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

Examples

Example 1

Input
matrix = [["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
matrix = [["0","1"],["1","0"]]
Output
1

Example 3

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

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

dp[i][j] = the side length of the largest all-1s square whose bottom-right corner is at (i, j).

Hint 2

If matrix[i][j] == 0, dp[i][j] = 0. Otherwise dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]).

Hint 3

Track the global max side as you fill the table; the answer is side * side.

Hint 4

Space optimization: only the previous row + the most recent diagonal value are needed.

Solution approach

Reveal approach

Bottom-up DP. Define dp[i][j] as the side length of the largest all-1s square with bottom-right at (i, j). For the first row and first column, dp[i][j] = matrix[i][j] (interpreted as int). For every inner cell where matrix[i][j] == 1, dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]); zero cells stay zero. Track maxSide across the fill. Return maxSide * maxSide. Why the min of three: the new square is limited by the smallest square abutting it from the three neighbors that share a side or corner. Space optimization: keep a 1D dp row plus a single 'previous diagonal' scalar.

Complexity

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

Related patterns

  • dynamic-programming
  • grid-dp

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Amazon
  • Apple
  • Microsoft
  • Meta

More 2D Dynamic Programming practice problems

See all 2D Dynamic Programming problems →